#include <iostream>
#include <fstream>
using std::cout;
using std::cerr;
using std::clog;
using std::endl;
using std::ostream;
using std::ifstream;
using std::ios_base;
#include <assert.h>
#include <math.h>
#include <string>
using std::string;
#include "dirent.h"


template<typename TInfo>
class AVLUzly;

#define SCITANI '+'
#define ODCITANI '-'
#define NASOBENI '*'
#define DELENI '/'
#define ROVNOST '='
#define ZAOKROUHLOVACI_CHYBA_DOUBLE 0.000000001

//! Vyctova mnozina zobrazeni posloupnosti na prvky.
class TAG{
public:
    TAG & operator=(TAG & tag){
        this->_SLOVNIDRUH = tag._SLOVNIDRUH;
        this->_PAD = tag._PAD;
        return *this;
    }
	byte _SLOVNIDRUH;
	byte _PAD;
};


//! Vyctova mnozina zobrazeni posloupnosti na prvky.
class PDT_TAG:public TAG{
public:
       PDT_TAG(const byte & slovnidruh, const byte & pad){
          this->_SLOVNIDRUH = 0;
          this->_PAD = 1;
       }
};



//! Definice toho, ktery typovy prvek se pouziva.
//#define TYP_TAG PDT_TAG


//! Funkce vraci maximum ze dvou cisel. Trida je sablonovatelna.
template<typename TCislo>
const TCislo & Max(const TCislo & a, const TCislo & b){
	if(a>b)return a;
	return b;
}


//! Funkce, ktera vraci true, pokud je cislo v nejakem epsilonovem okoli nuly.
bool JeVOkoliNuly(double cislo, double okoli){

	// pokud mame nejakou zapornou hodnotu, prepneme se do zapornych cislech a hodnota okoli musi by MENSI:
	if(cislo<0){
		if(cislo > (-okoli))return true;
		return false;
	}else{
	// pokud mame kladnou hodnotu, hodnota okoli musi by VETSI
		if(cislo < (okoli))return true;
		return false;
	}
}


//! Trida, ktera implementuje aritmeticke operace nad ruznymi typu.
template<typename XCislo, typename YCislo>
class AritmetickeOperace{
public:
	static void Rovnost(XCislo & x, const YCislo & y){
		//return x+y;
		x = y;
	}

	static void PrictiK(XCislo & x, const YCislo & y){
		//return x+y;
		x += y;
	}

	static void OdectiOd(XCislo & x, const YCislo & y){
		//return x-y;
		x -= y;
	}

	static void Vynasob(XCislo & x, const YCislo & y){
		//return x*y;
		x *= y;
	}

	static void Vydel(XCislo & x, const YCislo & y){
		//return x/y;
		x /= y;
	}

	static XCislo & Vrat(XCislo & x){
		return x;
	}

};



//! Trida TVyjimka obstarava prace s vyjimkami.
class TVyjimka{

public:

	// Staticke promenne jsou dulezite predevsim pro typ, jakym bude vyjimka vypisovana:
	enum{
		// Zaporne staticke konstanty jsou urceny pro definovani typu vystupu:
		EXCEPTION_COLON = -1 // Typ vypisu t1 : t2
		// Kladne staticke konstanty jsou urceny pro definovani cisel chyb:
	};

	TVyjimka(const string & t1, const int & n1, const string & t2){
		// Konstruktor nacte prvni cast retezce, cislo chyby / typ vypisu - zaporna cisla, druhou cast retezce:

		this->_t1=t1;
		this->_t2=t2;
		this->_n1=n1;
	}

	//! Procedura vypisuje informace o vyjimce.
	void Tisk(ostream & out){
		out << "[Vyjimka :]" << endl;
		out << _t1 << " ";
		
		// V zavislosti na typu cisla ve vyjimce se vypise ruzny druh vyjimky:
		switch(_n1){
			case EXCEPTION_COLON:
				out << " : ";
				break;
			default:
				out << "[Exception #" << _n1 << "] ";
				break;
		};
		
		out << _t2 << "!" << endl;
	}
private:
	string _t1;
	string _t2;
	int _n1;
};

//! Operator<< tiskne typ TVyjimka na vystup typu ostream.
ostream & operator<<(ostream & out, TVyjimka & x){
	x.Tisk(out);
	return out;
}

//! Trida ktera obecne zastupuje uzel v libovolne strukture. Do jednotlivych struktur se pouzivaji potomci.
template<typename TInfo>
class Uzel{
public:
	//! Vychozi konstruktor nuluje informaci. Vznika neplatny prvek.
	Uzel(){
		this->_info=NULL;
	}

	//! Funkce vraci logickou hodnotu, pokud instance tridy obsahuje platny prvek.
	bool JePlatny(){
		if(this->_info)return true;
		return false;
	}

	/*! Konstruktor tridy Uzel. Trida ma za ukol schranovat informace o uzlech BVS a nakonec cetnost prvku 
		* a samotne informace o prvku. Uzel je sablonovatelna trida, typ, kterym sablonujeme, je typem, ve kterem je ulozena
		* informace, kterou uzel nese. Sablonovanym typem je typ TInfo. Tento typ se nachazi ve tride Uzel jako ukazatel.
		* Tento typ musi mit definovany operatory porovnani <, > a operator << pro vypis. Vytvari se pomoci operatoru new s hodnotou
		* v zavorce. Muze jit o libovolny typ, napriklad int, double, string, apod. Informace o potomcich a rodicovi jsou
		* vzhledem ke kompatibilite, ktera je nutna, uchovany az v potomcich.
		*/
	Uzel(const TInfo & info){

		_info = new TInfo(info);
		// na zacatku je samozrejme levy i pravy syn prazdny, cetnost prvku je pri vytvoreni 1, vyvazeni vzhledem k synum 0 a rodice take nedosazujeme
	}

	~Uzel(){
		delete this->_info;
	}

	//! operator< porovnava informace v teto tride (Uzel) s tridou TInfo, porovnava samozrejme pouze nesenou informaci.
	bool operator<(const TInfo & info) const{
		if((*(this->_info))<info)return true;
		return false;
	}

	//! operator> porovnava informace v teto tride (Uzel) s tridou TInfo, porovnava samozrejme pouze nesenou informaci.
	bool operator>(const TInfo & info) const{
		if((*(this->_info))>info)return true;
		return false;
	}

	//! operator< porovnava informace v teto tride (Uzel) s jinou tridou Uzel<TInfo> & b, porovnava samozrejme pouze nesenou informaci.
	bool operator<(const Uzel<TInfo> & b) const{
		if((*this->_info) < (*b._info))return true;
		return false;
	}

	//! operator> porovnava informace v teto tride (Uzel) s jinou tridou Uzel<TInfo> & b, porovnava samozrejme pouze nesenou informaci.
	bool operator>(const Uzel<TInfo> & b) const{
		if((*this->_info) > (*b._info))return true;
		return false;
	}


	//! operator== porovnava informace v teto tride (Uzel) s jinou tridou typu TInfo, porovnava samozrejme pouze nesenou informaci.
	bool operator==(const TInfo & info) const{
		if((*this->_info) == (info))return true;
		return false;
	}

	Uzel operator+(const TInfo & y){
		return (*this->_info)+y;
	}

	//virtual static void Tisk(ostream & out)=0;
		//! Procedura, jejiz parametrem je ostream & out, tedy misto, kam chceme zapisovat. Funkce tam vytiskne informace o prvku.
		//! Funkce je virtualni s nutnosti definice v potomkovi.
	virtual void Tisk(ostream & out, const bool & tisknoutendl = false)=0;

	TInfo VratInfo(){
		return *this->_info;
	}

	TInfo * VratPInfo(){
		return this->_info;
	}

		
protected:
	//! V prvku * _info je nesena informace. Podle tohoto prvku je trida sablonovatelna. Typicky muze byt sablonovatelna jakymkoliv NEPOINTEROVYM typem.
	TInfo * _info;


	//! Procedura zrusi predchozi informaci (vcetne dealokace) a misto ni vytvori novou, kterou dosadi z argumentu.
	void DosadInfo(const TInfo & info){
       if(this->_info)delete this->_info;
       this->_info = new TInfo(info);     
    }
};




//! Prostor prostorSpojovySeznam sdruzuje tridy, ktere spolecne dohromady logicky tvori Spojovy seznam.
namespace prostorSpojovySeznam{

//! Sablonovana trida, ktera zastava funkci jednoho z uzlu spojoveho seznamu.
template<typename TInfo>
class SpojakUzel: public Uzel<TInfo>{
public:
	//! Prazdny konstruktor vytvori neplatny prvek.
	SpojakUzel(){
		this->_info = NULL;
	}

	//! Konstruktor, ktery vytvori uzel s informaci info.
	SpojakUzel(const TInfo & info){
		this->_info = new TInfo(info);
	}

	//! Destruktor v predkovi smaze obsah this->_info.
	~SpojakUzel(){
		//delete this ->_info;
		this->_rodic = NULL;
		this->_potomek = NULL;
	}

	//! Procedura nastavi potomka uzlu co na NULL. Predpokladem je platnost co.
	static void DosadPNULL(SpojakUzel<TInfo> * co){
		assert(co);
		co->_potomek=NULL;
	}

	//! Procedura nastavi rodice uzlu co na NULL. Predpokladem je platnost co.
	static void DosadRNULL(SpojakUzel<TInfo> * co){
		assert(co);
		co->_rodic=NULL;
	}

	//! Funkce vraci true, pokud ma co potomka. Predpokladem je platnost co.
	static bool MaP(SpojakUzel<TInfo> * co){
		assert(co);

		if(co->_potomek==NULL)return false;
		return true;
	}	

	//! Procedura navazuje vztah mezi rodicem a potomkem.
	static void NavazVztah(SpojakUzel<TInfo> * rodic, SpojakUzel<TInfo> * potomek){
		assert(rodic);
		if(potomek !=NULL){
			ZrusVztah(rodic,rodic->_potomek);
			//ZrusVztah(potomek->_rodic, potomek);
		}else{
			DosadPNULL(rodic);
		}

		// Spravne oboustranne navazani vztahu:
		
		rodic->_potomek = potomek;
		if(potomek){
			potomek->_rodic = rodic;
		}
	}

	//! Funkce vraci logickou hodnotu true v pripade, ze je rodi skutecne otcem potomka. Jinak vraci false.
	static bool JeNaslednik(SpojakUzel<TInfo> * rodic, SpojakUzel<TInfo> * potomek){
		if(potomek==NULL){
			if((rodic->_potomek == potomek))return true;
			return false;
		}
		if((potomek)&&(potomek->_rodic==rodic))return true;
		return false;
	}

	//! Procedura rusi vztah mezi rodicem a potomkem.
	static void ZrusVztah(SpojakUzel<TInfo> * rodic, SpojakUzel<TInfo> * potomek){
		if(!JeNaslednik(rodic,potomek))throw TVyjimka(string("prostorSpojovySeznam::SpojakUzel.ZrusVztah(")+ string(" ... , ... ") +string(")"),1,"Could not break a relationship (Parent-son relationship expected)");
		if(rodic == NULL) return;
		if(potomek == NULL) return;
	}

	//! Procedura vytiskne na parametr typu ostream informace z _info.
	virtual void Tisk(ostream & out, const bool & tisknoutendl = false){

		if(this->JePlatny()){
			out << *(this->_info);
			if(tisknoutendl){
				out << endl;
			}else{
				out << " ";
			}
		}else{
			cerr << "[SpojovySeznam :] Incorrect unit (signing end of block)" << endl;
		}
	}

	//! Procedura vytiskne z informace typu Slovo pouze Formu.
	void TiskForma(ostream & out){
		assert(this->_info);
		this->_info->TiskForma(out);
	}


	//! Funkce vraci rodice uzlu. Parametrem metody je prvek, jehoz rodice chceme ziskat
	static SpojakUzel<TInfo> * VratR(SpojakUzel<TInfo> * & prvek){
		assert(prvek);
		return prvek->_rodic;
	}

	//! Funkce vraci potomka uzlu. Parametrem metody je prvek, jehoz potomka chceme ziskat
	static SpojakUzel<TInfo> * VratP(SpojakUzel<TInfo> * & prvek){
		assert(prvek);
		return prvek->_potomek;
	}


protected:
	//! Pro uzel ve spojovem seznamu je nutne miti sveho predchudce.
	SpojakUzel<TInfo> * _rodic;
	//! Pro uzel ve spojovem seznamu je nutne miti sveho naslednika.
	SpojakUzel<TInfo> * _potomek;
};



//! Implementuje funkce ktere predstavuji dohromady spojovy seznam.
template<typename TInfo>
class SpojovySeznam{
typedef SpojakUzel<TInfo> TUzly;
public:
	//! Konstruktor spojoveho seznamu nastavi vsechny ukazatele na NULL a pocet prvku ve spojovem seznamu na 0.
	SpojovySeznam(){
		this->_pocet=0;
		this->_pocetneplatnych=0;
		this->_prvni = NULL;
		this->_posledni = NULL;
		this->_aktualni = NULL;
	}

	//! Destruktor smaze vsechny prvky, ktere zbyly.
	~SpojovySeznam(){

		// V prvku mazani bude vzdy aktualni prvek.
		this->_aktualni=this->_prvni;

		// Do prvku smazat si vzdy ulozime prvek, co budeme mazat
		SpojakUzel<TInfo> * smazat = NULL;

		// Pokud je aktualni prvek platny (a tedy i jeho naslednici jsou pravdepodobne platni)
		if(this->_aktualni)do{

			// Dosad do prvku na smazani aktualni prvek:
			smazat = this->_aktualni;

			// Aktualni prvek posun:
			this->_aktualni = TUzly::VratP(this->_aktualni);

			// Prvek smazat smaz :-)
			delete smazat;

			// Odecteme prislusny pocet:
			--this->_pocet;

			// A to delej, dokud je aktualni prvek stale platny:
		}while(this->_aktualni);

		if(this->_pocet+this->_pocetneplatnych != 0){
			throw TVyjimka("[~SpojovySeznam:] Dealocation was not successfull.", this->_pocet, " units have left.");
		}

		this->_prvni = NULL;
		this->_posledni = NULL;
		this->_aktualni = NULL;
	}


	/*void ProjdiFunkci(static void (*pf)(ostream&)){
		this->_aktualni =  this->_prvni;
		while(this->_aktualni){
			this->_aktualni = TUzly::VratP(this->_aktualni);
			this->_aktualni->pf;
		}
	}*/



	//! Procedura vytvori novy NEPLATNY uzel podle parametru, ktery zacleni na konec spojoveho seznamu.
	void PridejNeplatny(){
		SpojakUzel<TInfo> * novy = new SpojakUzel<TInfo>();
		TUzly::DosadPNULL(novy);

		// Novy prvek je pridan na konec:
		if(this->_prvni==NULL){
			this->_prvni = novy;
			this->_posledni = novy;
			TUzly::NavazVztah(novy,NULL);
			TUzly::DosadRNULL(novy);
		}else{
			TUzly::NavazVztah(this->_posledni, novy);
		}

		// Novym poslednim prvkem je prave pridany:
		this->_posledni = novy;

		// Nakonec nesmime zapomenout inkrementovat pocet neplatnych prvku:
		++this->_pocetneplatnych;
	}

	//! Procedura vytvori novy uzel podle parametru info typu TInfo, ktery zacleni na konec spojoveho seznamu.
	void Pridej(const TInfo & info){
		SpojakUzel<TInfo> * novy = new SpojakUzel<TInfo>(info);
		TUzly::DosadPNULL(novy);

		// Novy prvek je pridan na konec:
		if(this->_prvni==NULL){
			this->_prvni = novy;
			this->_posledni = novy;
			TUzly::NavazVztah(novy,NULL);
			TUzly::DosadRNULL(novy);
		}else{
			TUzly::NavazVztah(this->_posledni, novy);
		}

		// Novym poslednim prvkem je prave pridany:
		this->_posledni = novy;

		// Nakonec nesmime zapomenout inkrementovat pocet:
		++this->_pocet;
	}

	//! Funkce vraci pocet slov ve spojovem seznamu.
	unsigned long int VratPocet(){
		return this->_pocet;
	}


	//! Funkce vraci pocet neplatnych prvku ze spojoveho seznamu. Slozitost O(1), protoze vracime hodnotu, kterou si nacteme v prubehu nacitani.
	unsigned long int VratPocetNeplatnych(){
		return this->_pocetneplatnych;
	}


	//! Funkce nalezne prvek, ktery obsahuje info typu TInfo a vrati jej. Pokud prvek neexistuje, vraci NULL.
	SpojakUzel<TInfo> * Najdi(const TInfo & info){
		// Nastavime hledani na zacatek:
		this->_aktualni = this->_prvni;

		// Dokud je prochazeny prvek platny:
		while(this->_aktualni){

			// Zeptame se, jestli je aktualni prvek ten, co hledame
			if((*(this->_aktualni)) == (info)){

				// Pokud ano, skocime na Nalezeno
				goto Nalezeno;
				
			}else{

				// Pokud ne, hledame v potomkovi
				this->_aktualni = TUzly::VratP(this->_aktualni);
				
			}
		}
		return NULL;

Nalezeno:

		// Prvek jsme nasli, vratime jej:
		return this->_aktualni;
	}

	// Vytiskne prvky v posloupnosti do dalsiho neplatneho.
	bool TiskDoNeplatnehoPrvku(ostream & out, const bool & anulace = false){

		// Z predchozi iterace je aktualni na nekterem z neplatnych prvku (pokud na nem neni, jsme veprostred nektere vety.
		// Pokud pozadujeme anulaci, nastavime _aktualni na prvni prvek seznamu:
		if(anulace){
			this->_aktualni=this->_prvni;
		}else if(this->_aktualni==this->_posledni){
			// Pokud je aktualni prvek shodny s poslednim, vracime hlasku, ze uz zde nejsou zadne dalsi platne vety:
			cerr << "SpojovySeznam::TiskDoNeplatnehoPrvku(ostream & out) : No more valid sentences found!";
			return false;
		}else{
			// Jinak se nachazime uvnitr pole a muzeme se posunout:
			this->_aktualni = TUzly::VratP(this->_aktualni);
		}

		while(this->_aktualni){
			if(this->_aktualni->JePlatny()){
				this->_aktualni->TiskForma(out);
				out << " ";
			}else{
				out << endl << endl;
				break;
			}
			this->_aktualni = TUzly::VratP(this->_aktualni);
		}
		return true;
	}

	//! Procedura vytiskne vsechny prvky na vystup out.
	void Tisk(ostream & out, const bool & tisknoutendl = false){
		this->_aktualni = this->_prvni;

		while(this->_aktualni){
			this->_aktualni->Tisk(out,tisknoutendl);
			this->_aktualni = TUzly::VratP(this->_aktualni);
		}

		out << endl;
	}

	//! Pokud se aktualni prvek rovna poslednimu, vraci funkce true.
	bool JeKonec(){
		if(this->_aktualni == this->_posledni)return true;
		return false;
	}

	//! Procedura najde a smaze prvek s infem info.
	void Smaz(const TInfo & info){
		// Nejdrive se prvek pokusime najit:
		SpojakUzel<TInfo> * hledej = Najdi(info);

		// Pokud bylo hledani neuspesne, vyhodime chybovou hlasku:
		if(hledej==NULL){
			cerr << "prostorSpojovySeznam::SpojovySeznam.Smaz(" << info << ") : Searched unit hasn't been found!" << endl;
			return;
		}else{
			
			// Pokud jsme nasli, otestujeme, jestli je mazany prvek prvnim prvkem:
			if(TUzly::VratR(hledej)==NULL){

				// Pokud je prvnim prvkem, novym prvnim prvkem je jeho potomek
				this->_prvni = TUzly::VratP(hledej);
				if(TUzly::MaP(hledej))TUzly::DosadRNULL(TUzly::VratP(hledej));
				//TUzly::ZrusVztah(hledej, TUzly::VratP(hledej));
			}else{

				// Pokud neni prvnim prvkem, normalne zrusime vztah
				TUzly::NavazVztah(TUzly::VratR(hledej),TUzly::VratP(hledej));
			}
			delete (hledej);
			--this->_pocet;

			if(this->_pocet==0){
				this->_prvni=NULL;
				this->_posledni=NULL;
				this->_aktualni=NULL;
			}
		}
	}
protected:
	SpojakUzel<TInfo> * _prvni;
	SpojakUzel<TInfo> * _posledni;
	SpojakUzel<TInfo> * _aktualni;
	unsigned long int _pocet;
	unsigned long int _pocetneplatnych;
};


template<typename TInfo>
class SpojovySeznam_Vandas: public prostorSpojovySeznam::SpojovySeznam<TInfo>{
public:
	TInfo * VratPrvni(){
		this->_aktualni = this->_prvni;
		if(!this->_aktualni)return NULL;
		return this->_aktualni->VratPInfo();
	}

	TInfo * VratDalsi(){
		if(this->_aktualni == NULL)return NULL;
		this->_aktualni = SpojakUzel<TInfo>::VratP(this->_aktualni);
		if(this->_aktualni == NULL)return NULL;
		return this->_aktualni->VratPInfo();
	}

};

}; // konec prostoru spojovy seznam





//! Prostor prostorAVL sdruzuje tridy, ktere spolecne dohromady logicky tvori AVL stromy.
namespace prostorAVL{

//! Trida supluje funkci uzle v AVL strome.
template<typename TInfo>
class AVLUzel: public ::Uzel<TInfo>{
public:
	/*! Potomek tridy Uzel uchovava informace o levem a pravem synovi,
	* o rodici (pokud je NULL, jde o koren stromu), pro potreby AVL stromu uchovava vyvazeni uzlu.
	* Vychozi vstupy pro konstruktor jsou trida popisujici informace o Uzlu a cetnost, ktera je vychozim nastavenim dana na 1.*/
	AVLUzel(const TInfo & info, const double & cetnost=1){
		//this->_info = new TInfo(info);
		this->DosadInfo(info);
		this->_levy=NULL;
		this->_pravy=NULL;
		this->_cetnost=cetnost;
		this->_rodic=NULL;
		this->_balance=0;
		// na zacatku je samozrejme levy i pravy syn prazdny, cetnost prvku je pri vytvoreni 1, vyvazeni vzhledem k synum 0 a rodice take nedosazujeme
	}

	//! Destruktor AVLUzel. O this->_info se postara destruktor predka, jmenovite ~Uzel<TInfo>.
	~AVLUzel(){
		this->_levy = NULL;
		this->_pravy = NULL;
		this->_cetnost = 0;
		this->_rodic = NULL;
		this->_balance = 0;
	}

	
	/*! Procedura dosadi cetnost prvku. Cetnost je cislo typu double, to proto, aby mohla byt pocitana nejen celociselne (v pripade
	* specialnich operaci nad AVL stromem). Vychozim nastavenim pro pricteni k cetnosti je cislo 1. Navratova hodnota neni.
	*/
	void DosadCetnost(const double & hodnota){
		this->_cetnost = hodnota;
	}

	/*! Procedura zvysuje cetnost prvku. Cetnost je cislo typu double, to proto, aby mohla byt pocitana nejen celociselne (v pripade
	* specialnich operaci nad AVL stromem). Vychozim nastavenim pro pricteni k cetnosti je cislo 1. Navratova hodnota neni.
	*/
	void ZvysCetnost(const double & hodnota=1){
		this->_cetnost= this->_cetnost + hodnota;
	}

	double VratCetnost(){
		//! Funkce vrati kopii cisla(typ double), ktere nam dava informaci o cetnosti prvku.

		return this->_cetnost;
	}

	/*! Procedura Tisk ma vystup na ostream & out, tedy misto, kam chceme zapisovat. Procedura tam vytiskne informace o prvku, 
	* za nim v zavorce jeho cetnost.
	*/
	virtual void Tisk(ostream & out, const bool & tisknoutendl){
		out << *(this->_info) << "(" << this->_cetnost << ")";
		if(tisknoutendl){
			out << endl;
		}else{
			out << " ";
		}
		
	}



// A nyni static metody, ktere byly puvodne v Uzly<TInfo> : // ---------------------------------------------------------

// template<typename TInfo>
//class AVLUzly{
//public:

	/*! Funkce vraci informace o hloubce typem unsigned int. Ta je vzdy nezaporna, tedy unsigned int. Pro lepsi pouzitelnost funkce je jedinym parametrem
	* ukazatel typu AVLUzel<TInfo>, ze ktereho funkce zacne prohledavat. Vraci hloubku hlubsiho podstromu(dle balance) zvysenou o 1.
	*/
	static unsigned int MaxHloubka(AVLUzel<TInfo> * vychozi){
		if(vychozi==NULL)return 0;
		if(vychozi->_balance==-1){
			return MaxHloubka(vychozi->_levy)+1;
		}else{
			return MaxHloubka(vychozi->_pravy)+1;
		}
		//return Max<unsigned int>(MaxHloubka(vychozi->_levy),MaxHloubka(vychozi->_pravy))+1;
	}

	/*! Procedura pro Levo-levou rotaci AVL stromu. Vstupnimi parametry jsou koren podstromu, ve kterem rotujeme a celkovy koren, ktery
	* MUSI byt vracen pointer-referenci, aby se puvodni promenna, tedy ta, ve ktere je informace o koreni ulozena, pripadne zmenila.
	* Informace o algoritmu, napriklad zde : ksvi.mff.cuni.cz/~holan/AVL-insert-rotace.swf (podle techto obrazku jsou pojmenovany promenne).
	* Dalsi informace napriklad zde : ksp.mff.cuni.cz/tasks/18/ksp18-4.pdf */
	static void LLRotace(AVLUzel<TInfo> * stred, AVLUzel<TInfo> * & koren){
		// Nejdrive potrebujeme zaznamenat koreny podstromu, ktere se budou presouvat:
		AVLUzel<TInfo> * B = stred;
		AVLUzel<TInfo> * A = stred->_pravy;
		AVLUzel<TInfo> * C = NULL;

		// Zaznamename si informace o rodici puvodniho korenu
		AVLUzel<TInfo> * rodic = stred->_rodic;

		// Potom musime zkontrolovat, zda prvek C muze existovat a podle toho mu prizpusobit dalsi vypocet:
		if(stred->_pravy){
			C = stred->_pravy->_levy;
		}else{
			C = NULL;
		};		

		// Podle definice levo-leve rotace zrusime nektere vztahy (zde velky pozor, mame oboustrane pruchozi uzly):
		ZrusVztah(A,C);
		ZrusVztah(B,A);

		// Podle toho, jestli byl koren podstromu, ve kterem rotujeme, korenem celeho stromu, navazeme rodice (ci zmenime udaj o koreni)
		if(rodic==NULL){
			koren = A;
		}else{
			ZrusVztah(rodic,B);
			NavazVztah(rodic,A);
		}

		// Podle toho, jestli je C platny uzel, navazeme vztah s B
		if(C){
			NavazVztah(B,C);
		}else{
			NavazPNULL(B);
		}

		NavazVztah(A,B);

		// Nakonec vyvazime balance.
		A->_balance = 0;
		B->_balance = 0;
	}

	//! Procedura pro provedeni levo-prave rotace, viz materialy a poznamky u LLRotace.
	static void LRRotace(AVLUzel<TInfo> * stred, AVLUzel<TInfo> * & koren){
		AVLUzel<TInfo> * B = stred;
		AVLUzel<TInfo> * A = stred->_levy;
		AVLUzel<TInfo> * C = stred->_levy->_pravy;
		AVLUzel<TInfo> * pC = C->_pravy;
		AVLUzel<TInfo> * lC = C->_levy;
		AVLUzel<TInfo> * rodic = stred->_rodic;

		ZrusVztah(B,A);
		ZrusVztah(A,C);
		ZrusVztah(C,pC);
		ZrusVztah(C,lC);

		if(rodic==NULL){
			koren = C;
		}else{
			ZrusVztah(rodic,B);
			NavazVztah(rodic,C);
		}

		NavazVztah(C,A);
		NavazVztah(C,B);

		// Je nutne zjistit, jakou hloubku maji jednotlive podstromy B a C- tahle cast je trochu prasarna, ale nikde jsem nenasel, jak ji obejit:
		int hpC=0;
		int hlC=0;
		int hlA=0;
		int hpB=0;

		hlA = MaxHloubka(A->_levy);
		hpB = MaxHloubka(B->_pravy);

		if(lC){
			NavazVztah(A,lC);
			hlC = MaxHloubka(lC);
		}else{
			NavazPNULL(A);
		}
		
		if(pC){
			NavazVztah(B,pC);
			hpC = MaxHloubka(pC);
		}else{
			NavazLNULL(B);
		}	

		B->_balance = hpB - hpC;
		A->_balance = hlC - hlA;
		// Nakonec vyvazeni C
		C->_balance=0;
	}

	//! Procedura pro provedeni pravo-leve rotace, viz materialy a poznamky u LLRotace.
	static void RLRotace(AVLUzel<TInfo> * stred, AVLUzel<TInfo> * & koren){
		AVLUzel<TInfo> * B = stred;
		AVLUzel<TInfo> * A = stred->_pravy;
		AVLUzel<TInfo> * C = stred->_pravy->_levy;
		AVLUzel<TInfo> * pC = C->_pravy;
		AVLUzel<TInfo> * lC = C->_levy;
		AVLUzel<TInfo> * rodic = stred->_rodic;

		ZrusVztah(B,A);
		ZrusVztah(A,C);
		ZrusVztah(C,pC);
		ZrusVztah(C,lC);

		if(rodic==NULL){
			koren = C;
		}else{
			ZrusVztah(rodic,B);
			NavazVztah(rodic,C);
		}

		NavazVztah(C,A);
		NavazVztah(C,B);

		// Je nutne zjistit, jakou hloubku maji jednotlive podstromy B a C - tahle cast je trochu prasarna, ale nikde jsem nenasel, jak ji obejit:
		int hpC=0;
		int hlC=0;
		int hpA=0;
		int hlB=0;

		hpA = MaxHloubka(A->_pravy);
		hlB = MaxHloubka(B->_levy);

		if(pC){
			NavazVztah(A,pC);
			hpC = MaxHloubka(pC);
		}else{
			NavazLNULL(A);
		}
		
		if(lC){
			NavazVztah(B,lC);
			hlC = MaxHloubka(lC);
		}else{
			NavazPNULL(B);
		}

		B->_balance = hlC - hlB;
		A->_balance = hpA - hpC;

		// Nakonec vyvazeni C
		C->_balance=0;		
	}

	//! Procedura pro provedeni pravo-prave rotace, viz materialy a poznamky u LLRotace.
	static void RRRotace(AVLUzel<TInfo> * stred, AVLUzel<TInfo> * & koren){
		AVLUzel<TInfo> * B = stred;
		AVLUzel<TInfo> * A = stred->_levy;
		AVLUzel<TInfo> * C = NULL;
		if(stred->_levy){
			C = stred->_levy->_pravy;
		}else{
			C = NULL;
		}
		AVLUzel<TInfo> * rodic = stred->_rodic;

		ZrusVztah(A,C);
		ZrusVztah(B,A);
		if(rodic==NULL){
			koren = A;
		}else{			
			ZrusVztah(rodic,B);
			NavazVztah(rodic,A);
		}

		if(C){
			NavazVztah(B,C);
		}else{
			NavazLNULL(B);
		}

		NavazVztah(A,B);				

		B->_balance=0;
		A->_balance=0;
	}

	//! Procedura do dvojreference na koren dosazuje uzel jako koren s nalezitosmi, ktere jsou k tomu treba.
	static void DosadKoren(AVLUzel<TInfo> ** koren, AVLUzel<TInfo> * uzel){
		if(uzel->_rodic)ZrusVztah(uzel->_rodic,uzel);
		(*koren)=uzel;
		uzel->_rodic=NULL;
	}

	//! Funkce vrati logickou hodnotu true, jestli je rodic, syn, typu AVLUzel<TInfo> ve vztahu rodic-pravy syn. Vstupem je pouze ukazatel AVLUzel na rodice a budouciho syna.
	static bool JePSyn(AVLUzel<TInfo> * rodic, AVLUzel<TInfo> * syn){
		if(rodic==NULL){
			return false;
		}
		if(rodic->_pravy){
			if(rodic->_pravy==syn)return true;
		}
		return false;
	}

	//! Funkce vrati logickou hodnotu true, jestli je rodic, syn, typu AVLUzel<TInfo> ve vztahu rodic-levy syn. Vstupem je pouze ukazatel AVLUzel na rodice a budouciho syna.
	static bool JeLSyn(AVLUzel<TInfo> * rodic, AVLUzel<TInfo> * syn){
		if(rodic==NULL){
			return false;
		}
		if(rodic->_levy){
			if(rodic->_levy==syn)return true;
		}
		return false;
	}

	//! Procedura pro navazani vztahu mezi rodicem a pravym synem v pripade, ze syn je NULL. Vstup je pouze ukazatel AVLUzel na rodice.
	static void NavazPNULL(AVLUzel<TInfo> * rodic){
		assert(rodic);
		if(rodic->_pravy){
			rodic->_pravy->_rodic=NULL;
		}
		rodic->_pravy=NULL;
		return;
	}

	//! Procedura pro navazani vztahu mezi rodicem a levym synem v pripade, ze syn je NULL. Vstup je pouze ukazatel AVLUzel na rodice.
	static void NavazLNULL(AVLUzel<TInfo> * rodic){
		assert(rodic);
		if(rodic->_levy){
			rodic->_levy->_rodic=NULL;
		}
		rodic->_levy=NULL;
		return;
	}

	//! Procedura navazuje vztah rodic-syn mezi dvema ukazateli na AVLUzel. Podminkou je platnost obou zucastnenych ukazatelu.
	static void NavazVztah(AVLUzel<TInfo> * rodic, AVLUzel<TInfo> * syn){
		assert(rodic);
		assert(syn);
		if((*syn)>(*rodic)){
			if(rodic->_pravy){
				rodic->_pravy->_rodic=NULL;
			}
			rodic->_pravy = syn;
			if(syn==NULL)return;
			syn->_rodic	= rodic;
		}else{
			if(rodic->_levy){
				rodic->_levy->_rodic=NULL;
			}
			rodic->_levy = syn;
			if(syn==NULL)return;
			syn->_rodic	= rodic;
		}
	}

	//! Procedura rusi vztah mezi rodicem a synem. Vstupem je ukazatel AVLUzel na rodice a syna. Lze aplikovat pouze na platneho rodice.
	static void ZrusVztah(AVLUzel<TInfo> * rodic, AVLUzel<TInfo> * syn){
		assert(rodic);
		if(syn==NULL)return; // jiz vyreseno :-)

		if(JePSyn(rodic,syn)){

			// V pripade, ze jde o praveho syna, smazeme jak informaci u rodice, tak u syna
			rodic->_pravy = NULL;
			syn->_rodic = NULL;
		}else if(JeLSyn(rodic,syn)){

			// V pripade, ze jde o leveho syna, smazeme jak informaci u rodice, tak u syna
			rodic->_levy = NULL;
			syn->_rodic=NULL;
		}else{

			// V pripade, ze vztah neexistuje, vypiseme na errout hlasku:
			cerr << "A relationship doesn't exists(expected parent - son relationship)" << endl;
		}
	}


	//! Procedura dosadi do reference na ukazatel typu AVLUzel leveho syna uzlu.
	static void DosadLS(AVLUzel<TInfo> * & uzel){
		assert(uzel);
		uzel=uzel->_levy;
	}

	//! Procedura dosadi do reference na ukazatel typu AVLUzel praveho syna uzlu.
	static void DosadPS(AVLUzel<TInfo> * & uzel){
		assert(uzel);
		uzel=uzel->_pravy;
	}

	//! Procedura dosadi do reference na ukazatel typu AVLUzel praveho syna uzlu.
	static AVLUzel<TInfo> * VratR(AVLUzel<TInfo> * & uzel){
		/*cout << "Vracim rodice " << uzel << endl;
		if(uzel){
			cout << *(uzel->_info); cout << endl;
		}*/

		assert(uzel);
		return uzel->_rodic;
	}

	//! Funkce vrati diky referenci na ukazatel typu AVLUzel leveho syna uzlu.
	static AVLUzel<TInfo> * VratLS(AVLUzel<TInfo> * & uzel){
		assert(uzel);
		return uzel->_levy;
	}

	//! Funkce vrati diky referenci na ukazatel typu AVLUzel praveho syna uzlu.
	static AVLUzel<TInfo> * VratPS(AVLUzel<TInfo> * & uzel){
		assert(uzel);
		return uzel->_pravy;
	}

	//! Funkce vrati logickou hodnotu, true v pripade, ze existuje pravy uzel vstupniho ukazatele typu AVLUzel, jinak false.
	static bool MaPS(AVLUzel<TInfo> * & uzel){
		assert(uzel);
		if(uzel->_pravy)return true;
		return false;
	}

	//! Funkce vrati logickou hodnotu, true v pripade, ze existuje levy uzel vstupniho ukazatele typu AVLUzel, jinak false.
	static bool MaLS(AVLUzel<TInfo> * & uzel){
		assert(uzel);
		if(uzel->_levy)return true;
		return false;
	}


	/*! Procedura vytiskne na ostream & out informace o podstromu. Pro lepsi pouzitelnost funkce je volitelne, kde podstrom zacina, diky
	* ukazateli na AVLUzel.
	*/
	static void Tisk(ostream & out, AVLUzel<TInfo> * uzel){

		// Ukonceni rekurze:
		if(!uzel)return;

		// Vytiskni levy podstrom:
		if(uzel->_levy){
			Tisk(out,uzel->_levy);
		}

		// Vytiskni aktualni prvek:
		uzel->Tisk(out);
		out << endl;

		// Vytiskni pravy podstrom:
		if(uzel->_pravy){
			Tisk(out,uzel->_pravy);
		}		
	}

	/*! Procedura propaguje z leveho syna smerem nahoru informaci o zmene stromu po insertu. Potrebuje k tomu informace o aktualnim korenu
	* (na pocatku otci pridaneho) a referenci na ukazatel do korene (pro pripadne rotovani v koreni a naslednou zmenu korene).
	*/
	static void PropagaceZleva(AVLUzel<TInfo> * opravovany, AVLUzel<TInfo> * & koren){
 
		// Je-li opravovany prvek neplatny, jsme v koreni, muzeme skoncit:
		if(opravovany == NULL) return;

		// Ma-li opravovany prvek vyvazeni, ktere prevazuje doleva
		if(opravovany->_balance == -1){

			// a navic je jeho levy syn take levicak, 
			if((opravovany->_levy->_balance==-1)){

				// provedeme pravo-pravou rotaci.
				RRRotace(opravovany, koren);
			}else

			// a navic je jeho levy syn pravicak, 
			if((opravovany->_levy->_balance==+1)){

				// provedeme levo-pravou rotaci.
				LRRotace(opravovany, koren);
			}
		}else{

		// Jinak se nezabyvame dalsimi vecmi, protoze kriticke je pouze pretizeni vlevo. Paklize nenastava, pouze zmenime aktualni vyvazeni 
		// "doleva", tedy odecteme 1 od balance, a posuneme problem o uroven vys, pokud nedoslo k vyvazeni.
			opravovany->_balance -= 1;

			// Paklize nenastalo vyvazeni prvku a existuje rodic, zeptame se, jaci jsme synove, at vime, kam propagovat.
			if((opravovany->_balance!=0) && (opravovany->_rodic)){

				// Pravy syn propaguje zprava:
				if(JePSyn(opravovany->_rodic,opravovany)){
					PropagaceZprava(opravovany->_rodic,koren);
				}else{

				// Levy syn propaguje zleva:
					PropagaceZleva(opravovany->_rodic,koren);						
				}
			}
		}
	}

	/*! Procedura propaguje z praveho syna smerem nahoru informaci o zmene stromu po insertu. Potrebuje k tomu informace o aktualnim korenu
	* (na pocatku otci pridaneho) a referenci na ukazatel do korene (pro pripadne rotovani v koreni a naslednou zmenu korene).
	*/
	static void PropagaceZprava(AVLUzel<TInfo> * opravovany, AVLUzel<TInfo> * & koren){
 
		// Je-li opravovany prvek neplatny, jsme v koreni, muzeme skoncit:
		if(opravovany == NULL) return;

		// Ma-li opravovany prvek vyvazeni, ktere prevazuje doprava
		if(opravovany->_balance == +1){

			// a navic je jeho levy syn take levicak, 
			if((opravovany->_pravy->_balance==-1)){

				// provedeme pravo-levou rotaci
				RLRotace(opravovany, koren);
			}else

			// a navic je jeho levy syn take pravicak, 
			if((opravovany->_pravy->_balance== +1)){

				// provedeme levo-levou rotaci
				LLRotace(opravovany, koren);
			}
		}else{
		// Jinak se nezabyvame dalsimi vecmi, protoze kriticke je pouze pretizeni vlevo. Paklize nenastava, pouze zmenime aktualni vyvazeni 
		// "doprava", tedy pricteme 1 k balanci, a posuneme problem o uroven vys, pokud nedoslo k vyvazeni.
			opravovany->_balance += 1;

			// Paklize nenastalo vyvazeni prvku a existuje rodic, zeptame se, jaci jsme synove, at vime, kam propagovat.
			if((opravovany->_balance!=0) && (opravovany->_rodic)){

				if(JePSyn(opravovany->_rodic,opravovany)){
					// Pravy syn propaguje zprava:
					PropagaceZprava(opravovany->_rodic,koren);
				}else{
					// Levy syn propaguje zleva:
					PropagaceZleva(opravovany->_rodic,koren);						
				}
			}
		}	
	}





	/*! Procedura propaguje z leveho syna smerem nahoru informaci o zmene stromu po insertu. Potrebuje k tomu informace o aktualnim korenu
	* (na pocatku otci pridaneho) a referenci na ukazatel do korene (pro pripadne rotovani v koreni a naslednou zmenu korene).
	*/
	static void PropagaceZpravaDel(AVLUzel<TInfo> * opravovany, AVLUzel<TInfo> * & koren){
 
		// Je-li opravovany prvek neplatny, jsme v koreni, muzeme skoncit:
		if(opravovany == NULL) return;

		AVLUzel<TInfo> * rodic = NULL;
		bool byllevy=false;
		bool bylpravy=false;

		// Ma-li opravovany prvek vyvazeni, ktere prevazuje doleva
		if(opravovany->_balance == -1){

			// a navic je jeho levy syn take levicak, 
			if((opravovany->_levy->_balance==-1)){

				// provedeme pravo-pravou rotaci
				rodic=opravovany->_rodic;
				if(JePSyn(rodic,opravovany)){
					bylpravy=true;
					byllevy=false;
				}else{
					bylpravy=false;
					byllevy=true;
				}

				RRRotace(opravovany, koren);

				// podle toho, jaky byl opravovany prvek potomek, propagujeme o uroven vys
				if(bylpravy){
					PropagaceZpravaDel(rodic,koren);
				}else{
					PropagaceZlevaDel(rodic,koren);
				}
			}else if(opravovany->_pravy->_balance== 0){
				RRRotace(opravovany, koren);
			}

			// a navic je jeho levy syn pravicak, 
			if((opravovany->_levy->_balance==+1)){

				// provedeme levo-pravou rotaci.
				LRRotace(opravovany, koren);
			}
		}else{

		// Jinak se nezabyvame dalsimi vecmi, protoze kriticke je pouze pretizeni vlevo. Paklize nenastava, pouze zmenime aktualni vyvazeni 
		// "doleva", tedy odecteme 1 od balance, a posuneme problem o uroven vys, pokud nedoslo k vyvazeni.
			opravovany->_balance -= 1;

			// Paklize nenastalo vyvazeni prvku a existuje rodic, zeptame se, jaci jsme synove, at vime, kam propagovat.
			if((opravovany->_balance!=0) && (opravovany->_rodic)){

				// Pravy syn propaguje zprava:
				if(JePSyn(opravovany->_rodic,opravovany)){
					PropagaceZpravaDel(opravovany->_rodic,koren);
				}else{

				// Levy syn propaguje zleva:
					PropagaceZlevaDel(opravovany->_rodic,koren);						
				}
			}
		}
	}

	/*! Procedura propaguje z praveho syna smerem nahoru informaci o zmene stromu po insertu. Potrebuje k tomu informace o aktualnim korenu
	*	(na pocatku otci pridaneho) a referenci na ukazatel do korene (pro pripadne rotovani v koreni a naslednou zmenu korene).
	*/
	static void PropagaceZlevaDel(AVLUzel<TInfo> * opravovany, AVLUzel<TInfo> * & koren){
 
		// Je-li opravovany prvek neplatny, jsme v koreni, muzeme skoncit:
		if(opravovany == NULL) return;

		AVLUzel<TInfo> * rodic = NULL;
		bool byllevy=false;
		bool bylpravy=false;

		// Ma-li opravovany prvek vyvazeni, ktere prevazuje doprava
		if(opravovany->_balance == +1){

			// a navic je jeho levy syn take levicak, 
			if((opravovany->_pravy->_balance==-1)){

				// provedeme pravo-levou rotaci
				RLRotace(opravovany, koren);
			}else

			// a navic je jeho levy syn take pravicak, 
			if((opravovany->_pravy->_balance== +1)){

				// provedeme levo-levou rotaci
				rodic=opravovany->_rodic;
				if(JePSyn(rodic,opravovany)){
					bylpravy=true;
					byllevy=false;
				}else{
					bylpravy=false;
					byllevy=true;
				}

				LLRotace(opravovany, koren);

				// podle toho, jaky byl opravovany prvek potomek, propagujeme o uroven vys
				if(bylpravy){
					PropagaceZpravaDel(rodic,koren);
				}else{
					PropagaceZlevaDel(rodic,koren);
				}

			} else if(opravovany->_pravy->_balance== 0){
				LLRotace(opravovany, koren);
			}
		}else{
		// Jinak se nezabyvame dalsimi vecmi, protoze kriticke je pouze pretizeni vlevo. Paklize nenastava, pouze zmenime aktualni vyvazeni 
		// "doprava", tedy pricteme 1 k balanci, a posuneme problem o uroven vys, pokud nedoslo k vyvazeni.
			opravovany->_balance += 1;

			// Paklize nenastalo vyvazeni prvku a existuje rodic, zeptame se, jaci jsme synove, at vime, kam propagovat.
			if((opravovany->_balance!=0) && (opravovany->_rodic)){

				if(JePSyn(opravovany->_rodic,opravovany)){
					// Pravy syn propaguje zprava:
					PropagaceZpravaDel(opravovany->_rodic,koren);
				}else{
					// Levy syn propaguje zleva:
					PropagaceZlevaDel(opravovany->_rodic,koren);						
				}
			}
		}	
	}



	/*static unsigned int VratPocet(AVLUzel<TInfo> * vychozi){
		//! Funkce vrati pocet originalnich uzlu, ktere jsou v podstrome s korenem typu ukazatel na AVLUzel<TInfo>.
		if(vychozi==NULL)return 0;
		return 1+(VratPocet(vychozi->_levy)+VratPocet(vychozi->_pravy));
	}*/


	/*! Funkce overi pro kazdy podstrom splnenost invariantu AVL stromu, tedy ze hloubka praveho a leveho podstromu se lisi maximalne o 1.
	* Funkce zvenku VZDY dostava jako parametr koren AVL stromu.
	* Navratova hodnota vstupniho volani je rozdil mezi vyskou leveho a praveho podstromu.*/
	static unsigned int KorektnostAVL(AVLUzel<TInfo> * vychozi){

		// Navrat z rekurze:
		if(vychozi==NULL)return 0;

		// Rekurzivne zjisti korektnost leveho a praveho podstromu:
		unsigned int hl = KorektnostAVL(vychozi->_levy);
		unsigned int hp = KorektnostAVL(vychozi->_pravy);

		// Pokud se prava a leva hloubka lisi o 1, pokud jsme byli zavolani nejakym rodicem, vratime informaci o hloubce zvysenou o 1 za aktualni prvek.
		if((hl-hp == 0)||(hp-hl==-1)||(hp-hl==+1)){
			if(vychozi->_rodic){
				return Max<unsigned int>(hl,hp)+1;
			}else{

				// Pokud uz rodic neexistuje, jsme v koreni a kontrola probehla v poradku:
				clog << "AVL tree has been successfully tested for validity of invariant." << endl;
				return hl-hp;
			}
		}

		// Pokud hloubky nejsou spravne, neco je spatne:
		cerr << "AVL tree inconsistency detected! Invariant is not valid anymore (All subtrees has to have a difference between depths greater or equal to -1 and less or equal to 1)." << endl;
		throw TVyjimka("AVL tree error", 1, "AVL tree inconsistent");
		return hl-hp;		
	}

//}; // konec Uzly<TInfo>


	//! Funkce zmeni cetnost prvku podle parametru c. Parametr dosadi do cetnosti.
	AVLUzel<TInfo> & operator=(const double & c){
		this->_cetnost=c;
		return *this;
	}

	//! Funkce zmeni cetnost prvku podle parametru c. Parametr pricte c k cetnosti.
	AVLUzel<TInfo> & operator+=(const double & c){
		this->_cetnost+=c;
		return *this;
	}

	//! Funkce zmeni cetnost prvku podle parametru c. Parametr odecte c od cetnosti.
	AVLUzel<TInfo> & operator-=(const double & c){
		this->_cetnost-=c;
		return *this;
	}

	//! Funkce zmeni cetnost prvku podle parametru c. Parametr vynasobi cetnost c.
	AVLUzel<TInfo> & operator*=(const double & c){
		this->_cetnost*=c;
		return *this;
	}

	//! Funkce zmeni cetnost prvku podle parametru c. Parametr vydeli cetnost c.
	AVLUzel<TInfo> & operator/=(const double & c){
		this->_cetnost/=c;
		return *this;
	}


protected:

// kvuli AVL stromum potrebujeme informaci o vyvazeni jednotlivych uzlu, protoze chceme mit potomky stejne jako rodice, musime az nyni
// definovat potomky a rodice;

	//! AVL strom potrebuje mit v kazdem uzlu informaci o levem synovi.
	AVLUzel * _levy;
	//! AVL strom potrebuje mit v kazdem uzlu informaci o rodici.
	AVLUzel * _rodic;
	//! AVL strom potrebuje mit v kazdem uzlu informaci o pravem synovi.
	AVLUzel * _pravy;
	//! AVL strom potrebuje mit v kazdem uzlu informaci o vyvazeni podstromu.
	int _balance;
	//! AVL strom potrebuje mit v kazdem uzlu informaci o cetnosti, s jakou se aktualni prvek vyskytuje.
	double _cetnost;
};







//! Trida, ktera reprezentuje AVL stromy. AVL stromy jsou specialni struktura pro praci s prvky. Vice informaci v kazde knizce o algoritmech.
template<typename TInfo>
class AVL{

typedef AVLUzel<TInfo> TUzel;
typedef TUzel TUzly;

public:

	/*! Konstruktor AVL stromu je prazdny, nastavuje hodnoty na vychozi, tedy nuluje pocet prvku a prvku celkem, nastavuje na hodnoty
	* NULL jak koren, tak aktualni prvek.
	*/
	AVL(){
		this->_originalnich=0;
		this->_celkem=0;
		this->_pruchodkorenem=0;
		this->_originalnich=0;
		this->_aktualnimaximalni=NULL;
		this->_koren=NULL;
		this->_aktualni=NULL;
	}

	/*! Destruktor kontroluje dealokaci vsech prvku, nastaveni korene a aktualniho prvku na NULL. Pri nespravnem poctu dealokovanych
	*	prvku konci vyjimkou typu TVyjimka.
	*/
	~AVL(){

		if(this->_koren)SmazUzelPriOdalokaci(this->_koren);
		this->_koren=NULL;
		this->_aktualni=NULL;
		this->_aktualnimaximalni = NULL;
		
		// Mozne nulovani promennych:
		// ? TODO

		if(this->_originalnich!=0)throw TVyjimka("Memory hasn't been cleaned exactly (",this->_originalnich," units have left!)");
	}

	/*! Procedura odalokuje vsechny prvky leveho podstromu, vsechny prvky praveho podstromu a nakonec odalokuje uzel typu ALVUzel<TInfo>.
	*	Nezapomene pri tom opomenout odecist 1 od pocet a prislusny pocet vyskytu z celkem.
	*/
	void SmazUzelPriOdalokaci(AVLUzel<TInfo> * A){

		assert(A);
		if(TUzly::MaLS(A))SmazUzelPriOdalokaci(TUzly::VratLS(A));
		if(TUzly::MaPS(A))SmazUzelPriOdalokaci(TUzly::VratPS(A));
		--this->_originalnich;
		this->_celkem=this->_celkem - (A->VratCetnost());
		delete A;
		return;
	}

	//! Funkce zvysuje cetnost aktualniho prvku.
	void ZvysAktualniCetnost(const double & c){
		this->_aktualni->ZvysCetnost(c);
	}

	//! Funkce vraci cetnost aktualniho prvku.
	double VratAktualniCetnost(){
		return this->_aktualni->VratCetnost();
	}

	//! Procedura prida uzel, ktery nese informaci info. Vstupnimi parametry jsou informace, kterou ma uzel nest a jeho vstupni cetnost.
	void Pridej(const TInfo & info, const double & cetnost=1){

		// Funkci Najdi nalezneme misto, kam novy prvek bude nalezet, popripade nalezneme prvek samotny:
		AVLUzel<TInfo> * kam = Najdi(info);

		// Pokud je prvek jeste nevlozeny, 
		if(kam==NULL){

			// vlozime do prvku nove vytvoreny prvek vcetne jeho cetnosti:
			kam = new AVLUzel<TInfo>(info, cetnost);
			
			if(_aktualni==NULL){
				// pokud se aktualni prvek, tedy prvek, ktery je predchudcem prvku kam (jeho budouci rodic), NULL, je to koren(a musime jej zmenit):
				TUzly::DosadKoren(&_koren,kam);
			}else{
				// pokud aktualni prvek neni typu NULL, nejde o koren, pripojime k nemu prvek kam:
				TUzly::NavazVztah(_aktualni,kam);

				// a nakonec posleme informaci do rodice(bud propagaci zprava nebo zleva, dle pripojeni), ze byl pripojen novy prvek, at se s tim vybalancuje:
				if(TUzly::JePSyn(_aktualni,kam)){
					TUzly::PropagaceZprava(_aktualni, _koren);
				}else{
					TUzly::PropagaceZleva(_aktualni, _koren);
				}
			}
	
			// pridali jsme novy prvek, zvysime pocet, ktery dava informaci o originalnich prvcich:
			++this->_originalnich;

			// a samozrejme take zvysime celkem, informaci o prvcich, ktere jiz nejsou originalni:
			this->_celkem+=cetnost;
		}else{
			// pokud prvek uz existuje, jenom zvysime o 1 jeho cetnost:
			kam->ZvysCetnost(cetnost);

			// nesmime zapomenout zvysit celkovy pocet:
			this->_celkem=this->_celkem+cetnost;
		}
	}


	/*! Funkce dostava informaci typu TInfo a vraci ukazatel typu AVLUzel na prvek, ktery jsme hledali, nebo na NULL.
	*	Behem vypoctu funkce meni interni promennou aktualni, takze ji nelze prohlasit za const. V promenne aktualni se
	*	po prubehu funkce nachazi posledni platny prvek, pres ktery byl prvek s informaci TInfo hledan.*/
	AVLUzel<TInfo> * Najdi(const TInfo & info){
		// Zacneme hledat v koreni:
		AVLUzel<TInfo> * hledej=_koren;
		// Otec aktualniho prvku je prazdny:
		this->_aktualni=NULL;

		// Pokud uz samotny koren neni platny, koncime
		if(!hledej)return NULL;

		// Dokud se nam dari prochazet pres platne prvky, 
		while(hledej){
			// kdyz je prvek vetsi nez info, jdeme vlevo:
			if((*hledej)>info){
				_aktualni=hledej;
				TUzly::DosadLS(hledej);
			// kdyz je prvek mensi nez info, jdeme vpravo:
			}else if((*hledej)<info){
				_aktualni=hledej;
				TUzly::DosadPS(hledej);
			// jinak mame rovnost a vracime se s ukazatelem hledej:
			}else return hledej;
		}

		// pokud jsme dosli az sem, urcite je hledej NULL, takze muzeme vratit bud hledej, nebo NULL:
		return hledej;
	}

	//! Funkce vraci hodnotu typu unsigned int, jakou nejvetsi hloubku strom ma.
	unsigned int MaxHloubka() const{
		return TUzly::MaxHloubka(this->_koren);
	}

	//! Funkce otestuje, zda realny pocet a napocitany pocet odpovidaji a podle toho vrati logickou hodnotu.
	unsigned int KontrolaPocet(AVLUzel<TInfo> * vychozi) const{
		if(vychozi==NULL)return 0;
		unsigned int levy=0;
		unsigned int pravy=0;
		if(vychozi)levy=KontrolaPocet(TUzly::VratLS(vychozi));
		if(vychozi)pravy=KontrolaPocet(TUzly::VratPS(vychozi));
		return 1+levy+pravy;
	}

	//! Funkce, ktera kontroluje, zda se od korene najde stejny pocet prvku, jako bylo naalokovano do promenne this->_originalnich.
	bool KontrolaPocet() const{
		if(KontrolaPocet(this->_koren) == this->VratPocetOriginalnich())return true;
		return false;
	}

	//! Funkce vraci hodnotu typu unsigned int, jaky pocet originalnich prvku strom ma.
	unsigned int VratPocetOriginalnich() const{
		return this->_originalnich;
	}

	//! Funkce vraci hodnotu typu double, jaky pocet prvku celkem strom ma.
	double VratCelkem() const{
		return this->_celkem;
	}

	//! Procedura tiskne udaje o AVL strome na parametr typu ostream & out.
	void AVL_Tisk(ostream & out){
		//TUzly::Tisk(out,_koren);
		Tisk(out);
		out << VratPocetOriginalnich() << " original units" << endl;
		out << VratCelkem() << " in summary" << endl;
		out << MaxHloubka() << " layers of depth" << endl;
	}

	//! Procedura tiskne na parametr typu ostream & out postupne cely strom zleva doprava.
	void Tisk(ostream & out){
		TInfo * x = this->VratPrvni();
		while(x){
			out << (*x) << " (" << this->_aktualni->VratCetnost() << "), ";
			x = this->VratDalsi();
		}

		out << endl;
		//TUzly::Tisk(this->_koren);

	}

	bool JeKorektni(){
		//! Funkce vraci logickou hodnotu true, pokud AVL strom splnuje invariant, ze hloubka podstromu v kazdem uzlu se lisi max o 1.

		int c=TUzly::KorektnostAVL(_koren);
		if((c>=-1) && (c<=1)) return true;
		return false;
	}

	//! Funkce navraci prvni prvek TInfo, tedy ten, ktery je ve strome zarazen nejvice vlevo.
	TInfo * VratPrvni(){
		// Nejdrive si nastavime this->_aktualni na Minimalni prvek. Navratova hodnota minimum je nejmensi prvek, do this->_aktualni
		// dosazuje funkce rodice tohoto prvku:
		if(this->_koren == NULL)return NULL;
		this->_aktualni = this->Minimum(this->_koren);

		// Zmenime si aktualne maximalni prvek:
		this->_aktualnimaximalni = this->_aktualni;

		// Nastavime pruchod korenem na vychozi hodnotu:
		this->_pruchodkorenem = 0;

		// Pokud mame platny prvek, vratime jeho pointerInfo
		if((this->_aktualni)&&(this->_aktualni->JePlatny())){
			return this->_aktualni->VratPInfo();
		}

		// Jinak vracime NULL
		return NULL;
	}



	//! Funkce navraci prvni prvek TInfo, tedy ten, ktery je ve strome zarazen nejvice vlevo.
	TInfo * VratPosledni(){
		// Nejdrive si nastavime this->_aktualni na Minimalni prvek. Navratova hodnota minimum je nejmensi prvek, do this->_aktualni
		// dosazuje funkce rodice tohoto prvku:
		if(this->_koren == NULL)return NULL;
		this->_aktualni = this->Maximum(this->_koren);

		// Zmenime si aktualne maximalni prvek:
		this->_aktualnimaximalni = this->_aktualni;

		// Nastavime pruchod korenem na vychozi hodnotu:
		this->_pruchodkorenem = 0;

		// Pokud mame platny prvek, vratime jeho pointerInfo
		if((this->_aktualni)&&(this->_aktualni->JePlatny())){
			return this->_aktualni->VratPInfo();
		}

		// Jinak vracime NULL
		return NULL;
	}


	// Funkce vrati hodnotu nejmensiho dalsiho prvku v linearnim pruchodu AVL stromem.
	TInfo * VratDalsi(){
		// Nejdrive si do this->_aktualni dosadi nejmensi dalsi prvek v pruchodu:
		this->VratNaslednika();

		// A nasledne, pokud je platny, navrati jeho nesenou informaci:
		if((this->_aktualni) && (this->_aktualni->JePlatny())){
			return this->_aktualni->VratPInfo();
		}else{
			// Vychozi konstruktor nenese zadnou hodnotu a tudiz je navraceny prvek neplatny:
			return NULL;
		}
	}


	// Funkce vrati hodnotu nejmensiho dalsiho prvku v linearnim pruchodu AVL stromem.
	TInfo * VratPredchozi(){
		// Nejdrive si do this->_aktualni dosadi nejmensi dalsi prvek v pruchodu:
		this->VratPredchudce();

		// A nasledne, pokud je platny, navrati jeho nesenou informaci:
		if((this->_aktualni) && (this->_aktualni->JePlatny())){
			return this->_aktualni->VratPInfo();
		}else{
			// Vychozi konstruktor nenese zadnou hodnotu a tudiz je navraceny prvek neplatny:
			return NULL;
		}
	}

protected:



	//! Funkce dosadi do this->_aktualni nejmensi dalsi prvek v linearnim pruchodu AVL stromu.
	AVLUzel<TInfo> * VratNaslednika(){
		AVLUzel<TInfo> * novy = NULL;

		// Pokud jsme korenem neprosli vice nez jednou:
		while(this->_pruchodkorenem<2){

			// Pokud vsak uzel nema rodice, jsme v koreni,
			if(this->_aktualni == NULL)TVyjimka("Unhandled exception",-1,"Troubles with ancestor!");
			if(TUzly::VratR(this->_aktualni)==NULL){

				// Zvysime pruhodkorenem o 1
				++this->_pruchodkorenem;
				if(this->_pruchodkorenem==2)goto Konec;
			}


			// Pokud ma aktualni uzel praveho syna a ten je vetsi nez docasna hodnota promenne this->_aktualnimaximalni,
			//if(TUzly::MaPS(this->_aktualni)&&(TUzly::VratPS(this->_aktualni)>(this->_aktualnimaximalni))){
			if( TUzly::MaPS(this->_aktualni) && ((*(TUzly::VratPS(this->_aktualni)))>(*(this->_aktualnimaximalni))) ){

				// Najdeme minimum v podstrome s timto synem:
				// Nove maximum je aktualni prvek, ktery je tak nastaven na otce minimalniho prvku tohoto podstromu
				this->_aktualni = this->Minimum(TUzly::VratPS(this->_aktualni));
				this->_aktualnimaximalni = this->_aktualni;

				// Prave aktualni prvek si navratime:
				return this->_aktualni;
			}else{
				// this->_aktualni nema praveho syna, musime jit pres nektereho rodice a to bud vlevo nebo vpravo:
				novy = TUzly::VratR(this->_aktualni);

				// Tohle je haluz, kdyz nastane situace, ze se dostaneme sem, aktualni prvek nema ani praveho syna, ani otce, 
				// nema kam jit, musime koncit:
				if(novy==NULL){
					goto Konec;
				}

				// Pokud jdeme do rodice, ktery je "napravo nahore", musime tuto hodnotu uvazit jako jeden z prvku:
				if(TUzly::JeLSyn(novy, this->_aktualni)){
					this->_aktualni = novy;
					this->_aktualnimaximalni = this->_aktualni;
					return this->_aktualni;
				}else{
					// Pokud jdeme pres rodice, ktery je "nalevo nahore", hodnota jiz byla uvazena v nekterem z predchozich pripadu:
					this->_aktualni = novy;
					return this->VratNaslednika();
				}
			}
		}

Konec:
		// Pokud probehl while cyklus neuspesne, dostali jsme se podruhe do korene, coz je neplatny stav, vracime NULL:
		this->_aktualni = NULL;
		return this->_aktualni;
	}



	//! Funkce dosadi do this->_aktualni nejvetsi mensi prvek v linearnim pruchodu AVL stromu.
	AVLUzel<TInfo> * VratPredchudce(){
		AVLUzel<TInfo> * novy = NULL;

		// Pokud jsme korenem neprosli vice nez jednou:
		while(this->_pruchodkorenem<2){

			// Pokud vsak uzel nema rodice, jsme v koreni,
			if(this->_aktualni == NULL)TVyjimka("Unhandled exception",-1,"Troubles with ancestor!");
			if(TUzly::VratR(this->_aktualni)==NULL){

				// Zvysime pruhodkorenem o 1
				++this->_pruchodkorenem;
				if(this->_pruchodkorenem==2)goto Konec;
			}


			// Pokud ma aktualni uzel praveho syna a ten je vetsi nez docasna hodnota promenne this->_aktualnimaximalni,
			//if(TUzly::MaPS(this->_aktualni)&&(TUzly::VratPS(this->_aktualni)>(this->_aktualnimaximalni))){
			if( TUzly::MaLS(this->_aktualni) && ((*(TUzly::VratLS(this->_aktualni)))<(*(this->_aktualnimaximalni))) ){

				// Najdeme minimum v podstrome s timto synem:
				// Nove maximum je aktualni prvek, ktery je tak nastaven na otce minimalniho prvku tohoto podstromu
				this->_aktualni = this->Maximum(TUzly::VratLS(this->_aktualni));
				this->_aktualnimaximalni = this->_aktualni;

				// Prave aktualni prvek si navratime:
				return this->_aktualni;
			}else{
				// this->_aktualni nema praveho syna, musime jit pres nektereho rodice a to bud vlevo nebo vpravo:
				novy = TUzly::VratR(this->_aktualni);

				// Tohle je haluz, kdyz nastane situace, ze se dostaneme sem, aktualni prvek nema ani praveho syna, ani otce, 
				// nema kam jit, musime koncit:
				if(novy==NULL){
					goto Konec;
				}

				// Pokud jdeme do rodice, ktery je "napravo nahore", musime tuto hodnotu uvazit jako jeden z prvku:
				if(TUzly::JePSyn(novy, this->_aktualni)){
					this->_aktualni = novy;
					this->_aktualnimaximalni = this->_aktualni;
					return this->_aktualni;
				}else{
					// Pokud jdeme pres rodice, ktery je "nalevo nahore", hodnota jiz byla uvazena v nekterem z predchozich pripadu:
					this->_aktualni = novy;
					return this->VratPredchudce();
				}
			}
		}

Konec:
		// Pokud probehl while cyklus neuspesne, dostali jsme se podruhe do korene, coz je neplatny stav, vracime NULL:
		this->_aktualni = NULL;
		return this->_aktualni;
	}







	/*! Funkce dostava ukazatel na koren podstromu a vraci ukazatel typu AVLUzel na prvek, ktery je minimalnim v podstromu.
	*	Behem vypoctu funkce meni interni promennou aktualni, takze ji nelze prohlasit za const. V promenne aktualni se
	*	po prubehu funkce nachazi rodic prvku, ktery je minimem.
	*/
	AVLUzel<TInfo> * Minimum(AVLUzel<TInfo> * vychozi){

		assert(vychozi);
		// Zacneme hledat v koreni podstromu:
		AVLUzel<TInfo> * hledej=vychozi;
		// Otec aktualniho prvku je prozatim rodicem minima:
		this->_aktualni=NULL;

		// Pokud uz samotny koren neni platny, koncime
		if(!hledej)return NULL;
		this->_aktualni=hledej;

		// Dokud se nam dari prochazet pres platne prvky, 
		while(TUzly::VratLS(hledej)){
			// jdeme stale po minimu (vlevo):
			this->_aktualni=hledej;
			TUzly::DosadLS(hledej);
		}

		// pokud jsme dosli az sem, urcite je hledej minimum podstromu:
		return hledej;
	}


	/*! Funkce dostava ukazatel na koren podstromu a vraci ukazatel typu AVLUzel na prvek, ktery je minimalnim v podstromu.
	*	Behem vypoctu funkce meni interni promennou aktualni, takze ji nelze prohlasit za const. V promenne aktualni se
	*	po prubehu funkce nachazi rodic prvku, ktery je minimem.
	*/
	AVLUzel<TInfo> * Maximum(AVLUzel<TInfo> * vychozi){

		assert(vychozi);
		// Zacneme hledat v koreni podstromu:
		AVLUzel<TInfo> * hledej=vychozi;
		// Otec aktualniho prvku je prozatim rodicem minima:
		this->_aktualni=NULL;

		// Pokud uz samotny koren neni platny, koncime
		if(!hledej)return NULL;
		this->_aktualni=hledej;

		// Dokud se nam dari prochazet pres platne prvky, 
		while(TUzly::VratPS(hledej)){
			// jdeme stale po minimu (vlevo):
			this->_aktualni=hledej;
			TUzly::DosadPS(hledej);
		}

		// pokud jsme dosli az sem, urcite je hledej minimum podstromu:
		return hledej;
	}



	//! Informace o aktualnim prvku, pouzite hlavne pri hledani a po vkladani.
	AVLUzel<TInfo> * _aktualni;
	//! Zakoreneni celeho stromu je v promenne.
	AVLUzel<TInfo> * _koren;
	//! Pocet prvku celkem.
	double _celkem;
	//! Pocet originalnich prvku.
	unsigned long int _originalnich;
	
	//! Tyto dve promenne k AVL stromum ani tak moc nepatri, ale pomahaji pri linearnim pruchodu stromem:
	//! Pro potreby navstivenych a nenavstivenych casti stromu potrebujeme nejakou promennou, kde si prochazku budeme "pamatovat"
	unsigned int _pruchodkorenem;
	//! No a pro pruchod je treba vedet, cim uz jsme prosli a cim jeste ne:
	AVLUzel<TInfo> * _aktualnimaximalni;
};


template<typename TInfo>
class AVL_Vandas;


}; // konec jmenneho prostoru prostorAVL







//! Prostor prostorVstup poskytuje programu moznost pracovat nad ruznymi vstupy. Tridy vstupu jsou potomky tridy ifstream.
namespace prostorVstup{

#define TYPTAG 0
#define TYPFORMA 1
#define TYPLEMMA 2
#define TYPSLOVO 3
#define TYPKONECVETY 4
#define TYPKONECDOKUMENTU 5
#define TYPNEZNAMY 6


//! Trida slovo sdruzuje logicke metody pro praci se slovem.
class Slovo{
public:
friend ostream & operator<<(ostream & out, Slovo & slovo);


	//! Funkce, ktera vrati z informaci o slove pouze slovni druh. MODIFIKACE pro ruzne vstupy!
	static const char VratSlovniDruh(const string & informace){
		return informace.at(0);
	}

	/*! Prazdny konstruktor dosadi do vsech promennych implicitni hodnoty, kterymi jsou prazdne retezce. Predevsim prazdny slovni druh indikuje
	* neplatne slovo.
	*/
	Slovo(){
		this->_lemma=string("");
		this->_informace=string("");
	}

	//! Parametricky konstruktor, ktery vyplni analogicke promenne z tridy.
	Slovo(string lemma, string slovnidruh){
		this->_lemma=lemma;
		this->_informace=slovnidruh;
	}

	//! Operator= prekopiruje hodnoty jednotlivych promennych z promenne typu Slovo.
	Slovo & operator=(const Slovo & b){
		if(this==&b)return *this;
		this->_lemma=b._lemma;
		this->_informace=b._informace;
		return *this;
	}

	/*! Operator< porovna aktualni instanci s instanci v parametru funkce. Nejdrive se porovnava rovnost na lemmata, potom rovnost na
	*	slovni druh. V pripade pruchodu se povazuji slova za stejna (jina instance stejneho objektu).
	*/
	bool operator>(const Slovo & b) const{
		if(this->_lemma > b._lemma)return true;

		// Zde si definujeme, co vsechno z informaci chceme, aby se porovnavalo:
		const char (*atributslovnidruh)(const string &);

		atributslovnidruh = Slovo::VratSlovniDruh;

		if((this->_lemma==b._lemma)&&
			(atributslovnidruh(this->_informace) > atributslovnidruh(b._informace))
			)return true;
		return false;
	}

	/*! Operator< porovna aktualni instanci s instanci v parametru funkce. Nejdrive se porovnava rovnost na lemmata, potom rovnost na
	* slovni druh. V pripade pruchodu se povazuji slova za stejna (jina instance stejneho objektu).
	*/
	bool operator<(const Slovo & b) const{
		if(this->_lemma < b._lemma)return true;

		// Zde si definujeme, co vsechno z informaci chceme, aby se porovnavalo:
		const char (*atributslovnidruh)(const string &);

		atributslovnidruh = Slovo::VratSlovniDruh;

		if((this->_lemma==b._lemma)&&
			(atributslovnidruh(this->_informace) < atributslovnidruh(b._informace))
			)return true;
		return false;
	}


	//! Operator porovnani na typ Slovo.
	bool operator==(const Slovo & b) const{
		// Rovnost nastane pouze v pripade rovnosti vsech promennych:

		// Zde si definujeme, co vsechno z informaci chceme, aby se porovnavalo:
		const char (*atributslovnidruh)(const string &);

		atributslovnidruh = Slovo::VratSlovniDruh;

		if((this->_lemma == b._lemma)&&
			(atributslovnidruh(this->_informace) == atributslovnidruh(b._informace))
			)return true;
		return false;
	}



	//! Procedura dosadi do aktualni instance promenne z parametru.
	void DosadSlovo(string lemma, string tag, string forma){
		this->_lemma=lemma;
		this->_informace=tag;
	}


protected:
	string _lemma;
	string _informace;
}; // konec tridy Slovo



//! Operator<< pro vypis typu Slovo na vystup typu ostream.
ostream & operator<<(ostream & out, prostorVstup::Slovo & slovo){
	out << slovo._lemma << "(" << slovo._informace << ")"; // << slovo._forma << "(" 
	return out;
}


//! Trida FSlovo pracuje s entitou slovo, ktera v sobe obsahuje informaci o lemmatu, slovnim druhu a forme slova.
class FSlovo{
public:
friend ostream & operator<<(ostream & out, prostorVstup::FSlovo & slovo);


	//! Funkce, ktera vrati z informaci o slove pouze slovni druh. MODIFIKACE pro ruzne vstupy!
	static const char VratSlovniDruh(const string & informace){
		return informace.at(0);
	}

	/*! Prazdny konstruktor dosadi do vsech promennych implicitni hodnoty, kterymi jsou prazdne retezce. Predevsim prazdny slovni druh indikuje
	* neplatne slovo.
	*/
	FSlovo(){
		this->_lemma=string("");
		this->_informace=string("");
		this->_forma=string("");
	}

	//! Parametricky konstruktor, ktery vyplni analogicke promenne z tridy.
	FSlovo(string lemma, string slovnidruh, string forma){
		this->_lemma=lemma;
		this->_informace=slovnidruh;
		this->_forma=forma;
	}

	//! Operator= prekopiruje hodnoty jednotlivych promennych z promenne typu Slovo.
	FSlovo & operator=(const FSlovo & b){
		if(this==&b)return *this;
		this->_lemma=b._lemma;
		this->_forma=b._forma;
		this->_informace=b._informace;
		return *this;
	}

	//! Procedura dosadi do aktualni instance promenne z parametru.
	void DosadSlovo(string lemma, string tag, string forma){
		this->_lemma=lemma;
		this->_forma=forma;
		this->_informace=tag;
	}

	//! Operator porovnani pro entity typu FSlovo.
	bool operator==(const FSlovo & b) const{

		// Zde si definujeme, co vsechno z informaci chceme, aby se porovnavalo:
		const char (*atributslovnidruh)(const string &);

		atributslovnidruh = FSlovo::VratSlovniDruh;

		if((this->_lemma == b._lemma)&&
			(atributslovnidruh(this->_informace) == atributslovnidruh(b._informace))
			)return true;
		return false;
	}

	/*! Operator< porovna aktualni instanci s instanci v parametru funkce. Nejdrive se porovnava rovnost na lemmata, potom rovnost na
	* slovni druh. V pripade pruchodu se povazuji slova za stejna (jina instance stejneho objektu).
	*/
	bool operator>(const FSlovo & b) const{
		if(this->_lemma > b._lemma)return true;

		// Zde si definujeme, co vsechno z informaci chceme, aby se porovnavalo:
		const char (*atributslovnidruh)(const string &);

		atributslovnidruh = FSlovo::VratSlovniDruh;

		if((this->_lemma==b._lemma)&&
			(atributslovnidruh(this->_informace) > atributslovnidruh(b._informace))
			)return true;
		return false;
	}

	/*! Operator< porovna aktualni instanci s instanci v parametru funkce. Nejdrive se porovnava rovnost na lemmata, potom rovnost na
	* slovni druh. V pripade pruchodu se povazuji slova za stejna (jina instance stejneho objektu).
	*/
	bool operator<(const FSlovo & b) const{

		if(this->_lemma < b._lemma)return true;

		// Zde si definujeme, co vsechno z informaci chceme, aby se porovnavalo:
		const char (*atributslovnidruh)(const string &);

		atributslovnidruh = FSlovo::VratSlovniDruh;

		if((this->_lemma==b._lemma)&&
			(atributslovnidruh(this->_informace) < atributslovnidruh(b._informace))
			)return true;
		return false;
	}


	void TiskForma(ostream & out){
		out << this->_forma;
	}

protected:
	string _lemma;
	string _forma;
	string _informace;

}; // konec tridy Slovo

//! Operator<< pro vypis FSlovo na vystup typu ostream.
ostream & operator<<(ostream & out, FSlovo & slovo){
	out << slovo._lemma << "(" << slovo._informace << ")"; // << slovo._forma << "(" 
	return out;
}


//! Trida, ktera implementuje praci se vstupem. Vstup je vtipne potomkem tridy ifstream, takze implicitne dedi nektere jeho uzitecne metody.
template<typename TSlovo>
class Vstup:public ifstream{
public:
	//! Konstruktor nastavi priznaky vstupu na neplatne, protoze je bezparametrovy.
	Vstup(){
		this->_platnostprvku = false;
		this->_ok = false;
	}

	~Vstup(){
		this->Zavri();
	}

	//! Funkce vraci const char * se jmenem oteviraneho vstupu.
	const char * VratCharPJmeno(){
		return this->_jmeno.c_str();
	}

	//! Procedura pro otevreni souboru pro vstup s nalezitostmi.
	void Otevri(string & jmenosouboru){
		// Otevreme soubor pomoci interni funkce:
		this->open(jmenosouboru.c_str(),ios_base::in);

		// Z konstruktoru predka vime, ze promenna _ok oznacujici pruchodnost vstupu je nastavena na false
		// this->_ok=false;

		// Pokud se otevreni nepovedlo, vyhodi program Vyjimku:
		if(!this->is_open())throw TVyjimka("File could not be opened", 1, "error counted (check the filename)");

		// Ulozime si jmeno souboru do promenne:
		this->_jmeno = jmenosouboru;

		// Jinak nastavujeme pruchodnost vstupu na true :-)
		this->_ok=true;
	}

	//! Funkce pro uzavreni vstupu.
	bool Zavri(){

		// Zavreme vstup zdedenou metodou:
		try{
			this->close();
		}catch(...){
			// Paranoia v pripade, ze se nepovedlo vstup zavrit:
			return false;
		}

		// Nastavime pripravitelnost vstupu na false:
		this->_ok=false;

		return true;
	}


	//! Funkce vrati aktualni slovo a nacte dalsi slovo ze souboru.
	bool Nacti(TSlovo & slovo){
		
		// Nejakym zpusobem ziska slovo a informaci o tom, jestli je platne
		this->_platnostprvku = ZiskejSlovo(this->_aktualnislovo);

		// Nacte si do navratove hodnoty slovo aktualni slovo:
		slovo = this->_aktualnislovo;

		// Pokud se neco pokazilo - typicky konec vstupu, oznacime to v promenne _ok
		if(!this->good())this->_ok=false;

		// Navrat platnosti prvku:
		return this->_platnostprvku;
	}


	//! Funkce odebira ze vstupu slovo. Jako argument ma referenci na slovo, ktere se zmeni a vraci logickou hodnotu, zda jde o platne slovo.
	bool operator-=(TSlovo & slovo){
		return this->Nacti(slovo);
	}

	virtual bool ZiskejSlovo(TSlovo & slovo)=0;

	//! Nacte jednu radku ze vstupniho souboru
	bool NactiRadku(string & tmp){
		tmp = string("");
		if(_ok){
			_ok=PrectiRadku(tmp);
		}else{
			_ok=false;
			if(this->is_open())this->close();
		}
		return _ok;
	}

	bool JeKonec(){
		return !(this->_ok);
	}

protected:
	TSlovo _aktualnislovo;
	bool _ok;
	bool _platnostprvku;
	string _jmeno;

	bool PrectiRadku(string & tmp){
         //! Precte jeden radek pomoci funkce std::getline()

		std::getline(*((ifstream*)this),tmp);
		if(this->good())return true;

		this->_ok=false;
		if(this->is_open())this->close();
		return false;
	}

}; // konec tridy Vstup


//! Pretizeny operator >> pro zapis do promenne typu prostorVstup::Slovo.
bool operator>>(Vstup<prostorVstup::Slovo> & in, prostorVstup::Slovo & slovo){
	return in -= slovo;
	//return in >> slovo;
}

//! Pretizeny operator >> pro zapis do promenne typu prostorVstup::FSlovo.
bool operator>>(Vstup<prostorVstup::FSlovo> & in, prostorVstup::FSlovo & slovo){
	return in -= slovo;
	//return in >> slovo;
}


//! Trida je potomkem tridy Vstup. Implementuje vstup ze souboru typu PML z projektu PDT (Prague Dependency Treebank)
template<typename TSlovo>
class VstupPDT:public Vstup<TSlovo>{
public:
	//! Konstruktor VstupPDT, jakozto potomek tridy Vstup, ktera je potomkem tridy ifstream. Jedinym argumentem je jmeno oteviraneho souboru.
	VstupPDT(string jmenosouboru){
		this->Otevri(jmenosouboru);
	}

	//! Destruktor cerpa predevsim ze predka, kde se odalokuji vsechny promenne a uzavre vstup.
	~VstupPDT(){
	}


	//! Funkce ze vstupu odebere slovo, pripadne delici znak bloku. Pokud je slovo platne, vraci true, pokud ne, vraci false(oznacuje konec bloku)
	bool ZiskejSlovo(TSlovo & slovo){

		// Nacteni slova ze vstupu:
		return DosadSlovo(slovo);

		//?  Porovnani se slovnikem povolenych/nepovolenych slov:
		//? if(slovo == string("by"))return true;

	}


	//! Overuje, zda je v nactenem radku sledovany parametr
	bool JeVRetezci(string & tmp, const string & hledany){
		if((tmp.rfind("<"+hledany+" ")!=string::npos)||(tmp.rfind("<"+hledany+">")!=string::npos)){
			return true;
		}
		return false;
	}

	//! Extrahuje z promenne tmp (ktera je parovou znackou) extrakt (pouze jeji vnitrek) 
	void ExtrahujObsahParoveZnacky(string tmp, string & extrakt){
		unsigned int it=tmp.find_first_of(">");
		tmp=tmp.substr(it+1,tmp.size());
		it=tmp.find_first_of("<");
		tmp=tmp.substr(0,it);
		extrakt=tmp;
	}

	//! Vyhleda cast vstupniho souboru, ktera nas zajima
	int NajdiPozadovanyRetezec(string & tmp, string & extrakt){

		extrakt=string("");
		if(JeVRetezci(tmp,"lemma")){
			ExtrahujObsahParoveZnacky(tmp,extrakt);
			return TYPLEMMA;
		}else if(JeVRetezci(tmp,"form")){
			ExtrahujObsahParoveZnacky(tmp,extrakt);
			return TYPFORMA;
		}else if(JeVRetezci(tmp,"tag")){
			ExtrahujObsahParoveZnacky(tmp,extrakt);
			return TYPTAG;
		}else if(JeVRetezci(tmp,"/s")){
			return TYPKONECVETY;
		}
		return TYPNEZNAMY;
	}


	//! Implementace virtualni funkce, ktera nam nacte typ TSlovo
	bool DosadSlovo(TSlovo & slovo){ // string & forma, string & lemma, char & tag, R & hodnota

		string tmp;
		int stav=TYPSLOVO;
		bool okforma=false, oklemma=false, oktag=false;
		string extrakt;
		int typ=0;
		//hodnota=1;
		string forma, lemma, tag;

		while(this->NactiRadku(tmp)&&(!(okforma&&oklemma&&oktag))){                                                 
			typ=NajdiPozadovanyRetezec(tmp,extrakt);
			switch(typ){
			case TYPTAG:
				tag=extrakt; //.at(0);
				oktag=true;
				break;
			case TYPFORMA:
				forma=extrakt;
				okforma=true;
				break;
			case TYPLEMMA:
				lemma=extrakt;
				oklemma=true;
				break;
			case TYPKONECVETY:
				return false;
			case TYPNEZNAMY:
			default:
				break;
			}
		}

		if(this->_ok==false){
			//stav=TYPKONECDOKUMENTU;
			return false;
		}else{
			//stav=TYPSLOVO;
			slovo.DosadSlovo(lemma,tag,forma);
			return true;
		}
	}
}; // konec tridy VstupPDT



}; // konec jmenneho prostoru prostorVstup





//! Prostor prostorDokument sjednocuje dokumenty, ktere se uvazuji ze dvou hledisek - jedno hledisko je ciste statisticke a to druhe je naprosto obecne.
namespace prostorDokument{

//! Sablonovana trida dokument je abstraktnim predkem pro dalsi tridy, ktere supluji funkci dokumentu.
template<typename TSlovo>
class Dokument{
public:
protected:

	//! Funkce vraci logickou hodnotu true v pripade, ze vstup je v poradku a pripraven k nacitani. Metoda je protected a mohou ji volat jen potomci.
	bool TestPlatnehoVstupu(prostorVstup::Vstup<TSlovo> & in){

		if(in.JeKonec()){

			// V pripade ze je vstup vycerpan, program vraci vyjimku:
			throw TVyjimka(in.VratCharPJmeno(),TVyjimka::EXCEPTION_COLON,"File has been used yet! (Try to avoid using of file before using it here)");
		}

		// Proces probehl v poradku, vracime true:
		return true;
	}

	~Dokument(){
		//! Destruktor je prazdny.
	}

};


//! Trida obycejny dokument je nastrojem pro kompletaci promennych pod jednu "dokumentovou" strechu.
template<typename TSlovo>
class ObycejnyDokument : public Dokument<TSlovo>{

public:
	//! Konstruktor Obycejny dokument nacte ze vstupu typu prostorVstup::Vstup<TSlovo> slova do Spojoveho seznamu. Pritom zavede
	//! do statistik i neplatna slova, ktera jsou mezi ostatni vlozena jako oddelovace.
	ObycejnyDokument(prostorVstup::Vstup<TSlovo> & in){

		// Nyni budeme nacitat slova do promenne slovo, ktera je sablonovatelneho typu:
		TSlovo slovo;

		this->_slova = new prostorSpojovySeznam::SpojovySeznam<TSlovo>();

		// Dokud jsme nedocetli vstup do konce:
		while(!in.JeKonec()){ // in.good()

			// Pokud lze ze vstupu uloupnout platne slovo, pridame jej
			if(in >> slovo){
				this->_slova->Pridej(slovo);
			}else{
				// Pokud lze uloupnout uz jen neplatne slovo, pridame neplatne slovo a zvysime pocet neplatnych slov o 1
				// Pokud jsme vsak uloupli posledni vetu a nasleduje uz jen konec dokumentu, overime, jestli mame neplatny prvek pridat:
				if(!in.JeKonec())this->_slova->PridejNeplatny();
			}
		}

		in.Zavri();
	}

	~ObycejnyDokument(){
		delete this->_slova;
		this->_slova = NULL;
	}

	//! Funkce vraci pocet vet, ktere se nachazeji v dokumentu. Ziskame je malym trikem a to tak, ze vratime pocet neplatnych prvku
	//! (koncu bloku)
	unsigned long int VratPocetVet(){
		return this->_slova->VratPocetNeplatnych();
	}

	//! Funkce vraci pocet slov v datove strukture.
	unsigned long int VratPocetSlov(){
		return this->_slova->VratPocet();
	}

	//! Procedura vytiskne aktualni vetu, pri tisku prvni vety musime uvest hodnotu true pro anulaci.
	bool TiskniPrvniVetu(ostream & out){
		if(_slova.TiskDoNeplatnehoPrvku(out,true))return true;
		return false;
	}

	//! Procedura vytiskne aktualni vetu.
	bool TiskniDalsiVetu(ostream & out){
		if(!_slova.JeKonec()){

			// V ostatnich bezich je anulace nepripustna - vznikl by nekonecny cyklus:
			if(_slova.TiskDoNeplatnehoPrvku(out,false))return true;
		}
		return false;
	}

	//! Procedura vytiskne dokument na vystup typu ostream & out.
	void Tisk(ostream & out){
		_slova.Tisk(out,true);
	}

protected:
	// Obycejny dokument uchovavame ve spojovem seznamu, stejnak k jeho pruchodu pouzivame linearni zpusob.
	prostorSpojovySeznam::SpojovySeznam<TSlovo> * _slova;
};


//! Trida statisticky dokument sdruzuje statisticke informace dokumentu a v sikovne strukture(zde AVL strom) uchovava statisticke informace.
template<typename TSlovo>
class StatistickyDokument: public Dokument<TSlovo>{
friend class prostorAVL::AVL_Vandas<TSlovo>;
public:

	//! Konstruktor udela obvyklou vec a to, ze nacte z parametru typu prostorVstup::Vstup<TSlovo> statistiku na dokument.
	StatistickyDokument(prostorVstup::Vstup<TSlovo> & in){

		this->TestPlatnehoVstupu(in);

		this->_slova = new prostorAVL::AVL<TSlovo>();

		TSlovo slovo;
		while(in.good()){
			if(in >> slovo){
				// Je-li zpracovavane slovo platne:
				this->_slova->Pridej(slovo);

				if(!this->_slova->KontrolaPocet()){
					cout << "V PICI!!!!! : " << this->_slova->VratPocetOriginalnich() << endl;
					getchar();
				}

			}else{
				// toto slovo je neplatne, nebude se nijak zpracovavat
			}
		}

		in.Zavri();
	}

	//! Destruktor statistickeho dokumentu smaze akorat strukturu, ve ktere slova uchovavame.
	~StatistickyDokument(){
		delete (this->_slova);
		this->_slova=NULL;
	}

	//! Funkce vraci pocet originalnich slov ve statistickem dokumentu.
	unsigned int VratPocetOriginalnichSlov(){
		return this->_slova->VratPocetOriginalnich();
	}

	//! Funkce vraci pocet originalnich slov ve statistickem dokumentu.
	unsigned int VratPocetSlov(){
		return this->_slova->VratPocet();
	}
protected:
	// Struktura pro uchovani statistickych informaci:
	prostorAVL::AVL<TSlovo> * _slova;

	//! Funkce pro navrat struktury pro spratelene funkce (jmenovite konstruktor AVLVandas)
	prostorAVL::AVL<TSlovo> * & VratAVL_Vandas(){
		return this->_slova;
	}
};

}; // konec jmenneho prostoru prostorDokument









namespace prostorAVL{

//! Trida, ktera nad AVL stromy implementuje specialni aritmeticke operace, pro praci s nimi.
template<typename TInfo>
class AVL_Vandas: public AVL<TInfo>{
public:
	//! Konstruktor AVL_Vandas pouziva konstruktor predka.
	AVL_Vandas(){
	}

	//! Destruktor AVL_Vandas pouziva konstruktor predka, tato trida nema zadne svoje promenne.
	~AVL_Vandas(){
	}

	//! Konstruktor AVL_Vandas pouziva linearniho pruchodu prvku. Parametrem je reference na pointer predka.
	AVL_Vandas(prostorDokument::StatistickyDokument<TInfo> & statdokument){
		prostorAVL::AVL<TInfo> * predek = statdokument.VratAVL_Vandas();

		TInfo * x;
		x = predek->VratPrvni();
		while(x){
			// Pridava se informace o prvku vcetne jeho cetnosti:
			this->Pridej(*x, predek->VratAktualniCetnost());
			x = predek->VratDalsi();
		}
	}

	//! Konstruktor AVL_Vandas pouziva linearniho pruchodu prvku. Parametrem je reference na pointer predka.
	AVL_Vandas(AVL<TInfo> * & predek){
		TInfo * x;
		x = predek->VratPrvni();
		while(x){
			// Pridava se informace o prvku vcetne jeho cetnosti:
			this->Pridej(*x, predek->VratAktualniCetnost());
			x = predek->VratDalsi();
		}
	}

	//! Konstruktor AVL_Vandas pouziva linearniho pruchodu prvku. Parametrem je reference na predka.
	AVL_Vandas(AVL<TInfo> & predek){
		TInfo * x;
		x = predek.VratPrvni();
		while(x){
			// Pridava se informace o prvku vcetne jeho cetnosti:
			this->Pridej(*x, predek->VratAktualniCetnost());
			x = predek.VratDalsi();
		}
	}

	/*void PridejPodstrom(AVLUzel<TInfo> * vychozi, AVL<TInfo> & predek){
		this->Pridej(*(predek._aktualni->VratInfo()));
		if(predek._aktualni->_levy)this->PridejPodstrom(predek._aktualni->_levy, predek);
		if(predek._aktualni->_pravy)this->PridejPostrom(predek._aktualni->_pravy, predek);
	}*/


	//! Funkce, ktera z AVL stromu vybere ty nejcastejsi hodnoty(jejich pocet je dan parametrem), ostatni zrusi. POZOR! Tato funkce ma prozatim slozitost O(n*n) v poctu
	//! prvku stromu. Pro zrychleni by bylo potreba, aby se hodnoty z vektoru pridavaly postupne do AVL stromu. Pocita se vsak prozatim pouze s hodnotami, ktere budou radove
	//! mensi nez n, proto jsem toto zatim tolik neoptimalizoval.
	AVL_Vandas & OrezCetnostNaNejcastejsiHodnoty(const unsigned int & pocet){

		// Budeme prochazet AVL strom tak, ze budeme hledat postupne nejvesti maxima a jejich pocet budeme schranovat v promenne zbyva, ve ktere budeme postupne
		// tato maxima odcitat. V pripade, ze zbyva dosahne nuly, nasli jsme vsechna pozadovana maxima, muzeme koncit (mame je ulozena v poli, takze z nich muzeme
		// postavit novy strom a ten stary smazat :-)

		if(pocet>=this->VratPocetOriginalnich())return *this;

		// Nyni si do AVL stromu dame jednotlive cetnosti. Cetnosti u techto cetnosti znamenaji pocet vyskytu techto cetnosti u slov v dokumentu. 
		prostorAVL::AVL_Vandas<double> avlcetnosti;
		TInfo * x = this->VratPrvni();
		while(x){
			avlcetnosti.Pridej(this->VratAktualniCetnost(),1);
			x = this->VratDalsi();
		}

		// Nyni prijde nejzabavnejsi cast. Najdeme si minimum podle poctu cetnosti, ktere chceme vybrat tak, aby pocet vyssich nebo rovnajicich se cetnosti byl nejvyse roven
		// tomuto poctu cetnosti.


		double pocetmax = 0;
		long int zbyva = pocet;
		double * d = avlcetnosti.VratPosledni();
		while(d && (zbyva>0)){
			// Tohle je korektni operace, protoze jsme do cetnosti pridavali pouze hodnoty celociselne, viz o par radku vys. Pripadne varovani nemusime brat v potaz.
			pocetmax = avlcetnosti.VratAktualniCetnost();
			zbyva = zbyva - (long int)(floor(pocetmax));
			if(zbyva<=0)continue;
			d = avlcetnosti.VratPredchozi();
		}

		double min = (*d);
		


/*		TInfo * x = this->VratPrvni();
		double * maxmax = NULL;
		double max = 0;
		double c = 0;
		long int zbyva = pocet;
		long int pocetmax = 0;

		while(zbyva>0){
			x = this->VratPrvni();

			// Tady by se nam mohlo stat, ze hned napoprve narazime na zakazanou hodnotu, kterou vsak jiz jinde neprekoname a dojde k vecnaku... Proto tohle:
			if(maxmax){
				// Tady se nam to zase nemuze zacyklit, protoze jestli je zbytek pole uz slozen jen z nepovolenych hodnot, napocitali bychom to v minule iteraci nasledneho
				// cyklu:
				while(max >= (*maxmax)){
					x = this->VratDalsi();
					max = this->VratAktualniCetnost();
				}
			}else{
				max = this->VratAktualniCetnost();
			}

			pocetmax = 0;

			while(x){
				// Pokud je aktualni cetnost vetsi nez nejvetsi nalezene maximum, zmenime maximum, vynulujeme pocetmax na 1.
				// (pokud existuje maxmax, coz je promenna na kontrolu, zda jsme nevzali vicekrat jeden prvek(a ze nam nevraci tato funkce jen strom s maximem),
				// otestuje se, zda je max mensi nez tento maxmax)
				c = this->VratAktualniCetnost();
				if((c > max)&&((maxmax==NULL)||(c < (*maxmax)))){
					max = c;
					pocetmax = 1;
				// Pokud je tohle maximum a my ho znovu nasli, pripocitame pro nej dalsi vyskyt. Pri prvni iteraci musi byt prvni pocetmax rovno 0.
				}else if((c == max)&&((maxmax==NULL)||(c < (*maxmax)))){
					pocetmax += 1;
				}
				x = this->VratDalsi();
			}

			// nasli jsme maximum, odecteme

			if(maxmax)delete maxmax;
			maxmax = new double;
			(*maxmax) = max;
			zbyva -= pocetmax;
		}
		delete maxmax;
		maxmax = NULL;*/


		// Nyni, pokud je zbyva < 0, je posledni zahrnutelna hodnota v hodnote max, pocet minimalnich hodnot, ktere smime zahrnout v novem strome je (pocetmax + zbyva)
		// a ted uz jenom staci jeden pruchod, ktery to za nas vyresi ;)

		// TATO CAST MA JIZ SLOZITOST O(n*log n):
		unsigned int minimalnichhodnot = (long unsigned int)(floor(pocetmax)) + zbyva;
		prostorAVL::AVL_Vandas<TInfo> * novyavl = new prostorAVL::AVL_Vandas<TInfo>();

		// Nyni projdeme strom znovu, zahrneme jen hodnoty vetsi nez mezni hodnota.
		x = this->VratPrvni();
		while(x){
			if(this->VratAktualniCetnost()>min){
				novyavl->Pridej(*x, this->VratAktualniCetnost());
			}else if((this->VratAktualniCetnost()==min)&&(minimalnichhodnot>0)){
				novyavl->Pridej(*x, this->VratAktualniCetnost());
				--minimalnichhodnot;
			}
			x = this->VratDalsi();
		}

		// Ulozime si informace, ktere jsou klicoveho ze stareho stromu:
		AVLUzel<TInfo> * koren = this->_koren;
		unsigned int originalnich = this->_originalnich;
		double celkem = this->_celkem;

		// Povesime si do stromu nove vytvoreny avl strom, vcetne prepsani klicovych udaju
		this->_koren = novyavl->_koren;
		this->_originalnich = novyavl->_originalnich;
		this->_celkem = novyavl->_celkem;
		
		// No a aby se ten stary spravne dealokoval, tak si strukturu v novyavl upravime tak, abychom v ni mohli dealokovat stary strom:
		novyavl->_koren = koren;
		novyavl->_originalnich = originalnich;
		novyavl->_celkem = celkem;
		delete novyavl;
		novyavl = NULL;

		return *this;
	}


	
	//! Funkce pro aplikaci funkce typu double funkce(double) na kazdy prvek stromu, vraci sumu.
	double VratAplikaciUnarniFunkceRRNaCetnost(double &(*uk_funkce)(double&)){

		double suma = 0;
		double cetnost = 0;
		TInfo * x=NULL;
		x = this->VratPrvni();
		while(x){
			cetnost = this->VratAktualniCetnost();
			suma += uk_funkce(cetnost);
			x = this->VratDalsi();
		}

		return suma;
	}


	//! Funkce pro aplikaci funkce typu double funkce(double) na kazdy prvek stromu.
	void AplikujUnarniFunkci(double (*uk_funkce)(double)){
		//! DULEZITE UPOZORNENI: Aplikovat lze pouze funkce, ktere zachovavaji usporadani prvku! Jinak ve spojeni s AVL stromy
		//! nema jejich pouziti realny smysl! Po pripadnem uziti takove funkce se mohou linearni pruchody stromem chovat nevyzpytatelne
		//! a protoze se linearni pruchod pouziva v teto funkci, mohlo by v nejhorsim pripade napriklad dojit k zacykleni, protoze pruchod
		//! si jako jednu ze svych promennych uchovava maximalni prvek, ktery zatim prosel, coz pri pripadnym fuj-funkcich asi uplne nebude
		//! fungovat. Jak jsem ale napsal, funguje to tak proto, ze je to nad AVL stromem. Pripadne meneni posloupnosti, ktere se nacetly
		//! bude odporovat myslence, aby se tyto operace provedly co nejrychleji.
		//! Pripadne je nutne na toto pamatovat a funkce, resp. operatory u trid, podle kterych sablonujes,
		//! musis zaopatrit tak, aby funkce toto usporadani nerozbouravaly (tj. napriklad uzitim atributu, na kterem nezavisi trideni).

		TInfo * x;
		x = this->VratPrvni();
		while(x){
			*x = uk_funkce(*x);
			x = this->VratDalsi();
		}
	}
	
	//! Funkce pro aplikaci funkce typu double funkce(double) na kazdy prvek stromu.
	void AplikujUnarniFunkciNaCetnost(double (*uk_funkce)(double)){

		double cetnost=0;
		double modifikovanacetnost=0;
		TInfo * x=NULL;
		x = this->VratPrvni();
		while(x){
			this->_celkem -= (cetnost = this->VratAktualniCetnost());
			this->_aktualni->DosadCetnost(modifikovanacetnost = uk_funkce(cetnost));
			this->_celkem += modifikovanacetnost;
			x = this->VratDalsi();
		}
	}

	//! Funkce pro aplikaci funkce typu double funkce(TCislo &, const TCislo &) na kazdy prvek stromu.
	template<typename TCislo>
	void AplikujBinarniFunkciVRCR(void (*uk_funkce)(TCislo &, const TCislo &),const TCislo & c){
		//! Aplikuje funkci typu void fn(T &, const T &), kde const T & je predany parametr c.
		//! DULEZITE UPOZORNENI: Aplikovat lze pouze funkce, ktere zachovavaji usporadani prvku! Jinak ve spojeni s AVL stromy
		//! nema jejich pouziti realny smysl! Po pripadnem uziti takove funkce se mohou linearni pruchody stromem chovat nevyzpytatelne
		//! a protoze se linearni pruchod pouziva v teto funkci, mohlo by v nejhorsim pripade napriklad dojit k zacykleni, protoze pruchod
		//! si jako jednu ze svych promennych uchovava maximalni prvek, ktery zatim prosel, coz pri pripadnym fuj-funkcich asi uplne nebude
		//! fungovat. Jak jsem ale napsal, funguje to tak proto, ze je to nad AVL stromem. Pripadne meneni posloupnosti, ktere se nacetly
		//! bude odporovat myslence, aby se tyto operace provedly co nejrychleji.
		//! Pripadne je nutne na toto pamatovat a funkce, resp. operatory u trid, podle kterych sablonujes,
		//! musis zaopatrit tak, aby funkce toto usporadani nerozbouravaly (tj. napriklad uzitim atributu, na kterem nezavisi trideni).

		TInfo * x=NULL;
		x = this->VratPrvni();
		while(x){
			uk_funkce(*x, c);
			x = this->VratDalsi();
		}

	}

	//! Funkce vraci cetnost aktualniho prvku (typ double)
	double VratCetnostAktualnihoPrvku(){
		return this->_aktualni->VratCetnost();
	}

	//! Funkce zastresuje 4 zakladni aritmeticke operace pro pricitani typu double k typu TInfo. Vraci referenci na aktualni objekt, ktery
	//! proto musime menit. Parametry jsou const char & op, ktery zastupuje operator a konstanta const double & c, ktera zastupuje konstantu,
	//! se kterou hodlame operaci provadet.
	template<typename TCislo>
	AVL_Vandas & MujOperator(const char & op, const TCislo & c){

		TInfo * x;
		// Nadefinujeme si ukazatel na takovou funkci:
		void (*funkce)(AVLUzel<TInfo> &, const TCislo &);

		// Rozhodneme, ktera funkce se ma do ukazatele nahrat v zavislosti na obdrzenem parametru op typu char:
		switch(op){
			case SCITANI:
				funkce=AritmetickeOperace<AVLUzel<TInfo>,TCislo>::PrictiK;
				this->_celkem = this->_celkem + c;
				break;
			case ODCITANI:
				funkce=AritmetickeOperace<AVLUzel<TInfo>,TCislo>::OdectiOd;
				this->_celkem = this->_celkem - c;
				break;
			case NASOBENI:
				funkce=AritmetickeOperace<AVLUzel<TInfo>,TCislo>::Vynasob;
				this->_celkem = this->_celkem * c;
				break;
			case DELENI:
				funkce=AritmetickeOperace<AVLUzel<TInfo>,TCislo>::Vydel;
				this->_celkem = this->_celkem / c;
				break;
			case ROVNOST:
				funkce=AritmetickeOperace<AVLUzel<TInfo>,TCislo>::Rovnost;
				this->_celkem = this->_originalnich * c;
				break;
			default:
				// Pri nedodrzeni predepsanych funkci nam vyskoci nasledujici vyjimka:
				throw TVyjimka("Unsupported operator used",op," used.");
				return *this;
				break;
			}

		// A nyni uz klasicky - projdeme vsechny prvky a na kazdy zvlast po rade aplikujeme funkci, kterou jsme dosadili do ukazatele:
		x = this->VratPrvni();
		while(x){
			//funkce(*x, c);
			funkce(*this->_aktualni, c);
			x = this->VratDalsi();
		}
		return *this;		
	}

	//! Funkce pricita konstantu c a vraci *this, odkazujeme do obecnejsi funkce MujOperator, ktera pracuje s druhym parametrem typu double.
	AVL_Vandas & operator=(const double & c){
		return (MujOperator<double>(ROVNOST, c));
	}

	//! Funkce pricita konstantu c a vraci *this, odkazujeme do obecnejsi funkce MujOperator, ktera pracuje s druhym parametrem typu double.
	AVL_Vandas & operator+=(const double & c){
		return (MujOperator<double>(SCITANI, c));
	}

	//! Funkce nasobi konstantou c a vraci *this, odkazujeme do obecnejsi funkce MujOperator, ktera pracuje s druhym parametrem typu double.
	AVL_Vandas & operator*=(const double & c){
		return (MujOperator<double>(NASOBENI, c));
	}

	//! Funkce odecita konstantu c a vraci *this, odkazujeme do obecnejsi funkce MujOperator, ktera pracuje s druhym parametrem typu double.
	AVL_Vandas & operator-=(const double & c){
		return (MujOperator<double>(ODCITANI, c));
	}

	//! Funkce deli konstantou c a vraci *this, odkazujeme do obecnejsi funkce MujOperator, ktera pracuje s druhym parametrem typu double.
	AVL_Vandas & operator/=(const double & c){
		return (MujOperator<double>(DELENI, c));
	}


	//! Funkce je obecnym zpracovanim operaci + a - mezi tridami AVL_Vandas.
	AVL_Vandas & SpecialniOperatorAVL_VandasPLUSMINUS(const char & op, AVL_Vandas & b){

		// Pokud jsou oba cleny v operaci identicke
		if(this==&b){
			// Zjistime, co mame udelat v zavislosti na operatoru:
			switch(op){
				case SCITANI:
					// Pokud je scitame, odpovida to vynasobeni 2
					this->operator*=(2);
					break;
				case ODCITANI:
					// Pokud je odecitame, odpovida to vynasobeni 0
					this->operator*=(0);
					break;
				default:
					// Pokud nebyla zvolena platna operace pro volani, koncime vyjimkou:
					throw TVyjimka("[AVL_Vandas:] Unsupported operator",op,"used");
					break;
			}

			// Navracime ziskany vysledek:
			return *this;
		}

		// Pokud jsou oba cleny neidenticke, zavedeme si pomocnou promennou znamenko, ktera nam bude rikat, kterou operaci zpracovavame:
		double znamenko = 1;

		switch(op){
			case SCITANI:
				// Pro scitani bude znamenko +1
				znamenko = +1;
				break;
			case ODCITANI:
				// Pro odcitani bude znamenko -1
				znamenko = -1;
				break;
			default:
				// Opet pri nedodrzeni predepsanych operaci vyvolame vyjimku:
				throw TVyjimka("Unsupported operator",op,"used");
				break;
		}
		
		// A nyni k samotnemu vypoctu. Nejdrive potrebujeme ukazatele z obou struktur na aktualni prvek(prochazeno pri linearnim usporadani)
		TInfo * x;
		TInfo * y;

		AVL_Vandas * novyavl = new AVL_Vandas();

		// Zapocneme linearni pruchod:
		x = this->VratPrvni();
		y = b.VratPrvni();

		// Pro vsechna x a y projdeme pole, pokud neni v y nic, x se nemeni, alespon pri scitani a odcitani:
		while(x&&y){

			// V pripade, ze v nasem poli nemame nektere prvky z y, pridame je vcetne jejich cetnosti:
			while((y)&&((*x)>(*y))){
				novyavl->Pridej(*y, znamenko*(b.VratAktualniCetnost()));
				y = b.VratDalsi();
			}

			// Pokud mezitim dojde pole y, skoncime pricitani nebo odcitani k x, ostatni hodnoty zustavaji nemenne:
			if(!y)break;

			// V pripade, ze v nasem poli nemame nektere prvky z y, pridame je v jejich cetnosti:
			while((x)&&((*y)>(*x))){
				novyavl->Pridej(*x, this->VratAktualniCetnost());
				x = this->VratDalsi();
			}

			if(!x)break;

			// Pokud se prvky nahodou rovnaji, upravime cetnost u x podle cetnosti ziskane z y:
			if((*x)==(*y)){
				if((this->VratAktualniCetnost()+(znamenko)*(b.VratAktualniCetnost()))!=0){
					novyavl->Pridej(*x,this->VratAktualniCetnost()+(znamenko)*(b.VratAktualniCetnost()));
				}
				x = this->VratDalsi();
				y = b.VratDalsi();
			}
		}

		// Pokud je y platne, musime "dopridat" prvky, ktere nebyly v x, protoze predchozi while cyklus mohl skoncit tim, ze x==NULL
		while(y){
			novyavl->Pridej(*y, znamenko*(b.VratAktualniCetnost()));
			y = b.VratDalsi();
		}
		
		// Ulozime si informace, ktere jsou klicoveho ze stareho stromu:
		AVLUzel<TInfo> * koren = this->_koren;
		unsigned int originalnich = this->_originalnich;
		double celkem = this->_celkem;

		// Povesime si do stromu nove vytvoreny avl strom, vcetne prepsani klicovych udaju
		this->_koren = novyavl->_koren;
		this->_originalnich = novyavl->_originalnich;
		this->_celkem = novyavl->_celkem;
		
		// No a aby se ten stary spravne dealokoval, tak si strukturu v novyavl upravime tak, abychom v ni mohli dealokovat stary strom:
		novyavl->_koren = koren;
		novyavl->_originalnich = originalnich;
		novyavl->_celkem = celkem;
		delete novyavl;

		return *this;
	}

	//! Funkce dosazuje instanci tridy AVL_Vandas k this.
	/*! Funkce pricita instanci tridy AVL_Vandas a vraci *this, odkazujeme do obecnejsi funkce, ktera pracuje
	*	s druhym parametrem typu AVL_Vandas. Prvnim parametrem je typ operace.
	*/
	AVL_Vandas & operator=(AVL_Vandas & b){
		if(this->_koren)this->SmazUzelPriOdalokaci(this->_koren);
		this->_celkem = 0;
		this->_koren = NULL;
		
		if(this->_originalnich!=0){
			cerr << "Dealocation was not successful! " << this->_originalnich << "units have left." << endl;
			this->_originalnich = 0;
		}
		(*this) += b;
		return *this;
	}

	//! Funkce pricita instanci tridy AVL_Vandas k this.
	/*! Funkce pricita instanci tridy AVL_Vandas a vraci *this, odkazujeme do obecnejsi funkce, ktera pracuje
	*   s druhym parametrem typu AVL_Vandas. Prvnim parametrem je typ operace.
	*/
	AVL_Vandas & operator+=(AVL_Vandas & b){
		return this->SpecialniOperatorAVL_VandasPLUSMINUS(SCITANI,b);
	}

	//! Funkce odcita instanci tridy AVL_Vandas od this.
	/*! Funkce odcita instanci tridy AVL_Vandas a vraci *this, odkazujeme do obecnejsi funkce, ktera pracuje
	*	s druhym parametrem typu AVL_Vandas. Prvnim parametrem je typ operace.
	*/
	AVL_Vandas & operator-=(AVL_Vandas & b){
		return this->SpecialniOperatorAVL_VandasPLUSMINUS(ODCITANI,b);
	}

	//! Funkce nasobi this instanci tridy AVL_Vandas.
	/*! Funkce nasobi instanci tridy AVL_Vandas a vraci *this, odkazujeme do obecnejsi funkce, ktera pracuje
	*	s druhym parametrem typu AVL_Vandas. Prvnim parametrem je typ operace.
	*/
	AVL_Vandas & operator*=(AVL_Vandas & b){
		return this->SpecialniOperatorAVL_VandasKRATDELENO(NASOBENI,b);
	}

	//! Funkce deli instanci tridy AVL_Vandas.
	/*! Funkce deli instanci tridy AVL_Vandas a vraci *this, odkazujeme do obecnejsi funkce, ktera pracuje
	* s druhym parametrem typu AVL_Vandas. Prvnim parametrem je typ operace.
	*/
	AVL_Vandas & operator/=(AVL_Vandas & b){
		return this->SpecialniOperatorAVL_VandasKRATDELENO(DELENI,b);
	}


	//! Funkce je obecnym zpracovanim operaci + a - mezi tridami AVL_Vandas.
	AVL_Vandas & SpecialniOperatorAVL_VandasKRATDELENO(const char & op, AVL_Vandas & b){

		// Pokud jsou oba cleny v operaci identicke
		if(this==&b){
			// Zjistime, co mame udelat v zavislosti na operatoru:
			switch(op){
				case NASOBENI:
					// Neimplementovano!
					// Pokud je nasobime, odpovida to umocneni kazdeho prvku
					//this->operator*=(2);
					break;
				case DELENI:
					// Pokud je delime, odpovida to rovnosti jednicce, pokud mezi nimi neni 0(coz diky implementaci neni)
					this->operator=(1);
					break;
				default:
					// Pokud nebyla zvolena platna operace pro volani, koncime vyjimkou:
					throw TVyjimka("[AVL_Vandas:] Unsupported operator",op,"used");
					break;
			}

			// Navracime ziskany vysledek:
			return *this;
		}

		// A nyni k samotnemu vypoctu. Nejdrive potrebujeme ukazatele z obou struktur na aktualni prvek(prochazeno pri linearnim usporadani)
		TInfo * x;
		TInfo * y;

		// Zapocneme linearni pruchod:
		x = this->VratPrvni();
		y = b.VratPrvni();

		AVL_Vandas * novyavl = new AVL_Vandas();

		// Pro vsechna x a y projdeme pole, pokud neni v y nic, x se vyprazdni(zavedeme novy AVL_Vandas), alespon pri nasobeni a deleni:
		while(x&&y){

			// V pripade, ze v nasem poli nemame nektere prvky z y, neuvazujeme je v novem poli:
			while((y)&&((*x)>(*y))){
				y = b.VratDalsi();
			}

			// Pokud mezitim dojde pole y, skoncime pricitani nebo odcitani k x, ostatni hodnoty z x zmizi
			if(!y)break;

			// V pripade, ze v nasem poli nemame nektere prvky z y, pridame je v jejich cetnosti:
			while((x)&&((*y)>(*x))){
				x = this->VratDalsi();
			}

			if(!x)break;

			// Pokud se prvky nahodou rovnaji, upravime cetnost u x podle cetnosti ziskane z y:
			if((*x)==(*y)){
				switch(op){
					case NASOBENI:
						if((this->VratAktualniCetnost()*b.VratAktualniCetnost()) != 0){
							novyavl->Pridej(*x,this->VratAktualniCetnost()*b.VratAktualniCetnost());
						}
						break;
					case DELENI:
						if(b.VratAktualniCetnost()==0)throw TVyjimka("Dividing by zero!",-1,"One of AVL_Vandas structure has zero-member.");
						if((this->VratAktualniCetnost()/b.VratAktualniCetnost()) != 0){
							novyavl->Pridej(*x,this->VratAktualniCetnost()/b.VratAktualniCetnost());
						}
						break;
					default:
						TVyjimka("Unsupported operator",op,"used");
						break;
				}

				x = this->VratDalsi();
				y = b.VratDalsi();
			}
		}

		// Ostatni prvky ani v x, ani v y nas jiz nezajimaji

		AVLUzel<TInfo> * koren = this->_koren;
		unsigned int originalnich = this->_originalnich;
		double celkem = this->_celkem;

		this->_koren = novyavl->_koren;
		this->_originalnich = novyavl->_originalnich;
		this->_celkem = novyavl->_celkem;
		
		novyavl->_koren = koren;
		novyavl->_originalnich = originalnich;
		novyavl->_celkem = celkem;
		delete novyavl;

		return *this;
	}



	/*! Funkce kontroluje, zda soucet vsech hodnot v promenne celkem odpovida souctu cetnosti vsech prvku.
	* Pokud ano s nejakou chybou, dosadi soucet jako novy celkovy soucet.*/
	bool ZkontrolujRozdil(){

		// Inicializace:
		TInfo * x = NULL;
		x = this->VratPrvni();
		double soucet=0;

		while(x){
			// Prubezny soucet zvysim o aktualni cetnost:
			soucet += this->VratAktualniCetnost();

			// Vratim si dalsi prvek a iteruji:
			x = this->VratDalsi();
		}

		// Vracim rozdil souctu:

		// Pokud je rozdil mensi nez nejaka chyba, upravim aktualni promennou celkem a vracim nulovy rozdil:
		if(JeVOkoliNuly(this->_celkem - soucet, ZAOKROUHLOVACI_CHYBA_DOUBLE)){
			this->_celkem = soucet;
			return true;
		}else{
			//return this->_celkem - soucet;
			return false;
		}
	}





}; // konec tridy AVL_Vandas


}; // konec prostoruAVL





//! Prostor prostorCluster provadi clusterovani ziskanych informaci.
namespace prostorCluster{

//! Funkce z argumentem predavanym referenci(nikoliv konstantni) vraci druhou mocninu v referenci.
static double & _sqr(double & x){
	x*=x;
	return x;
}

//! Dopredna deklarace
template<typename TInfo>
class Clustery;

//! Trida Cluster sdruzuje funkce pro praci s clusterem.
template<typename TInfo>
class Cluster{
public:

	//! Konstruktor tridy cluster, prozatim prazdny.
	Cluster(prostorDokument::StatistickyDokument<prostorVstup::Slovo> & defdokument, const unsigned long int & max /*= 0*/){
		this->_centroid = new prostorAVL::AVL_Vandas<TInfo>(defdokument);
		this->_pocetdokumentu = 1;
		this->_maxpocetprvkucentroidu = max;

		// Pokud je maximalni pocet prvku v centroidu omezeny, orezeme pocet prvku v centroidu:
		if(this->_maxpocetprvkucentroidu>0){
			this->_centroid->OrezCetnostNaNejcastejsiHodnoty(max);
		}
		this->_obycdokumenty = NULL;
		this->_statdokumenty = NULL;
	}
	

	//! Funkce, ktera vraci podobnost dokumentu vuci aktualnimu clusteru.
	double VratPodobnostDokumentu(prostorDokument::StatistickyDokument<prostorVstup::Slovo> & statdokument){

		// Nejdrive si nacteme vektor zkoumaneho dokumentu do AVL_Vandas (budeme potrebovat aritmeticke operace):
		prostorAVL::AVL_Vandas<TInfo> * dokvektor = new prostorAVL::AVL_Vandas<TInfo>(statdokument);

		// Spocteme castecne soucty druhych mocnin pro centroid a pro statdokument:
		double sqrx = dokvektor->VratAplikaciUnarniFunkceRRNaCetnost(_sqr);
		double sqry = this->_centroid->VratAplikaciUnarniFunkceRRNaCetnost(_sqr);

		// Pro prazdne dokumenty nema smysl pomerovat podobnost:
		if((sqry==0) || (sqrx==0)){
			return -1; // neplatna(nesmyslna) hodnota podobnosti
		}

		// Nasledne dokvektor vynasobime centroidem a ziskame tak vrchni cast zlomku:
		(*dokvektor) *= (*this->_centroid);

		// Vrsek zlomku je soucet po vynasobeni:
		double z = dokvektor->VratCelkem();

		// Odalokace dokvektoru:
		delete dokvektor;
		dokvektor = NULL;

		return z/(sqrt(sqrx)*sqrt(sqry));
	}
	
private:
	friend class Clustery<TInfo>;
	//! Funkce prida dokument do clusteru a aktualizuje centroid
	void PridejDokument(prostorDokument::StatistickyDokument<prostorVstup::Slovo> & statdokument, prostorAVL::AVL_Vandas<prostorVstup::Slovo>* & idf){

		(*this->_centroid) *= ((this->_pocetdokumentu)/((double)(this->_pocetdokumentu+1)));
		
		// Kontrola : Co kdyby nahodou soucty nesedely...
		/*if(!(this->_centroid->ZkontrolujRozdil())){
			cerr << "Error of checking sum!" << endl;
		};*/

		prostorAVL::AVL_Vandas<TInfo> * dokvektor = new prostorAVL::AVL_Vandas<TInfo>(statdokument);
		(*dokvektor) *= (*idf);

		(*dokvektor) /= (this->_pocetdokumentu+1);

		(*this->_centroid) += (*dokvektor);
		if(this->_maxpocetprvkucentroidu>0){
			this->_centroid->OrezCetnostNaNejcastejsiHodnoty(this->_maxpocetprvkucentroidu);
		}

		delete dokvektor;
		dokvektor = NULL;
		++this->_pocetdokumentu;
	}


	prostorAVL::AVL_Vandas<TInfo> * _centroid;
	prostorDokument::ObycejnyDokument<TInfo> ** _obycdokumenty;
	prostorDokument::StatistickyDokument<TInfo> ** _statdokumenty;
	unsigned long int _maxpocetprvkucentroidu;
	unsigned int _pocetdokumentu;
}; // konec tridy Cluster


//! TODOOOOOOOOOOOOOO!
template<typename TInfo>
ostream & operator<<(ostream & out, prostorCluster::Cluster<TInfo> & cluster){
	return out;
}

//! Trida, ktera spravuje vice trid typu prostorCluster::Cluster.
template<typename TInfo>
class Clustery{
public:
	//! Konstruktor je temer prazdny.
	Clustery(double mezpodobnosti, const unsigned long int & maxprvkucentroidu = 0){
		this->_clustery = new prostorSpojovySeznam::SpojovySeznam_Vandas<prostorCluster::Cluster<TInfo> >();
		this->_mezpodobnosti = mezpodobnosti;
		this->_maxprvkucentroidu = maxprvkucentroidu;
	}

	//! Procedura prida mezi jiz existujici clustery dokument.
	void PridejDokument(prostorDokument::StatistickyDokument<prostorVstup::Slovo> & statdokument, prostorAVL::AVL_Vandas<prostorVstup::Slovo>* & idf){
		//this->_clustery
		prostorCluster::Cluster<TInfo> * x = this->_clustery->VratPrvni();
		prostorCluster::Cluster<TInfo> * nejcluster = NULL;
		double maxpodobnost = 0;
		double podobnost = 0;

		while(x){
			if((podobnost = x->VratPodobnostDokumentu(statdokument))>maxpodobnost){
				maxpodobnost = podobnost;
				nejcluster = x;
			}
			x = this->_clustery->VratDalsi();
		}

		if((this->_clustery->VratPocet()==0)||(maxpodobnost<this->_mezpodobnosti)){
			nejcluster = new prostorCluster::Cluster<TInfo>(statdokument,this->_maxprvkucentroidu);
			this->_clustery->Pridej(*nejcluster);
			delete nejcluster;
			nejcluster = NULL;
		}else{
			// Pridavame do jiz existujiciho clusteru:
			nejcluster->PridejDokument(statdokument, idf);
		}
	}

	unsigned int VratPocet(){
		return this->_clustery->VratPocet();
	}

private:
	prostorSpojovySeznam::SpojovySeznam_Vandas<prostorCluster::Cluster<TInfo> > * _clustery;
	double _mezpodobnosti;
	unsigned long int _maxprvkucentroidu;
};


}; // konec prostorCluster




//! Funkce pro nacteni souboru do struktury, vraci true, pokud se podari otevrit adresar a nacist soubory.
bool NactiSoubory(const char * curdir, prostorAVL::AVL<string> & avl_adresar){
/* check command line arguments */
/* print contents of directories listed in command line */
	int i = 1;

    DIR *dir;
    struct dirent *ent;

    /* open directory stream */
    dir = opendir (curdir);
    if (dir != NULL) {

      /* print all the files and directories within directory */
      while ((ent = readdir (dir)) != NULL) {
        //printf ("%s\n", ent->d_name);
		  if(!((strcmp(ent->d_name,".")==0)||(strcmp(ent->d_name,"..")==0))){
			  avl_adresar.Pridej(string(curdir)+string(ent->d_name));
		  }
      }
      
      closedir (dir);
	  return EXIT_SUCCESS;
    } else {
      /* could not open directory */
      perror ("");
      return EXIT_FAILURE;
    }
    i++;
  }





int main( int argc, char * argv[] ){
    
	try{
		// Pro zacatek definujeme dvojpointery na dokumenty a AVL stromy :
		unsigned int pocetvstupu = 0;
		prostorDokument::ObycejnyDokument<prostorVstup::FSlovo> ** dokumentyobyc = NULL;
		prostorDokument::StatistickyDokument<prostorVstup::Slovo> ** dokumentystat = NULL;
		prostorAVL::AVL_Vandas<prostorVstup::Slovo> ** vektorydokumentu = NULL;

		try{

			// NACITACI A TRENOVACI MODUL:
			// Nacteme si data z adresare, ktery zadame do promenne aktualniadresar. V adresari se mohou nalezat pouze platne
			// soubory typu PML z projektu PDT:
			prostorAVL::AVL<string> avl_adresar;
			char * aktualniadresar = "data/";

			// Pokud se z nejakeho duvodu nepovede otevrit adresar a nacist jmena souboru do promenne avl_adresar, koncime program
			// s chybou. Pravdepodobne byl zadan adresar, ktery je neplatny, nebo do nej uzivatel nema pristup:
			if(NactiSoubory(aktualniadresar, avl_adresar)){
				return -1;
			};

			// Do promenne pocetvstupu si dosadime pocet nalezenych souboru :
			pocetvstupu = avl_adresar.VratPocetOriginalnich();

			//prostorVstup::VstupPDT<prostorVstup::FSlovo> ** vstupyobyc = (prostorVstup::VstupPDT<prostorVstup::FSlovo> **)malloc(sizeof(prostorVstup::Vstup<prostorVstup::FSlovo>*)*(pocetvstupu+1));
			//prostorVstup::VstupPDT<prostorVstup::Slovo> ** vstupystat = (prostorVstup::VstupPDT<prostorVstup::Slovo> **)malloc(sizeof(prostorVstup::Vstup<prostorVstup::Slovo>*)*(pocetvstupu+1));

			// Naalokujeme dvojpointery
			// Obycejne dokumenty pro sekvencni pristup:
			dokumentyobyc = (prostorDokument::ObycejnyDokument<prostorVstup::FSlovo> **)malloc(sizeof(prostorDokument::ObycejnyDokument<prostorVstup::FSlovo>*)*(pocetvstupu+1));
			// Dokumenty pro tvoreni statistik:
			dokumentystat = (prostorDokument::StatistickyDokument<prostorVstup::Slovo> **)malloc(sizeof(prostorDokument::StatistickyDokument<prostorVstup::Slovo>*)*(pocetvstupu+1));
			// Dokumenty pointer
			vektorydokumentu = (prostorAVL::AVL_Vandas<prostorVstup::Slovo>**)malloc(sizeof(prostorAVL::AVL_Vandas<prostorVstup::Slovo>*)*(pocetvstupu+1));

			// Pomocne promenne pro otevreni vstupu pro jednotlive dokumenty:
			prostorVstup::Vstup<prostorVstup::FSlovo> * vstupobycdokument = NULL;
			prostorVstup::Vstup<prostorVstup::Slovo> * vstupstatdokument = NULL;

			// Nyni nacteni pole, do ktereho budeme ukladat tf ze vsech dokumentu:
			prostorAVL::AVL_Vandas<prostorVstup::Slovo>* tf = new prostorAVL::AVL_Vandas<prostorVstup::Slovo>();
			// Pomocne pole, se kterym budeme pridavat polozky do pole vndokumentech, ktere je pak pripraveno pro vypocet idf:
			prostorAVL::AVL_Vandas<prostorVstup::Slovo>* pomocne = new prostorAVL::AVL_Vandas<prostorVstup::Slovo>();;
			// Pole pro vypocet idf = tf / vndokumentech (pocitano po slozkach):
			prostorAVL::AVL_Vandas<prostorVstup::Slovo>* vndokumentech = new prostorAVL::AVL_Vandas<prostorVstup::Slovo>();;

			// Prvni soubor, ktery budu zpracovavat:
			string * s = avl_adresar.VratPrvni();
			for(unsigned int i=0; i < pocetvstupu; ++i){
				//vstupyobyc[i] = new prostorVstup::VstupPDT<prostorVstup::FSlovo>(*s);
				//vstupystat[i] = new prostorVstup::VstupPDT<prostorVstup::Slovo>(*s);

				// Obycejny dokument, otevreni jeho vstupu:
				vstupobycdokument = new prostorVstup::VstupPDT<prostorVstup::FSlovo>(*s);
				// Pripocteni pres vstup do pole obycejnych dokumentu:
				dokumentyobyc[i] = new prostorDokument::ObycejnyDokument<prostorVstup::FSlovo>(*vstupobycdokument);
				// Smazani docasneho vstupu dokumentu:
				delete vstupobycdokument;
					//dokumentyobyc[i] = new prostorDokument::ObycejnyDokument<prostorVstup::FSlovo>(prostorVstup::VstupPDT<prostorVstup::FSlovo>(*s));

				// Statisticky dokument, nacteni jeho vstupu:
				vstupstatdokument = new prostorVstup::VstupPDT<prostorVstup::Slovo>(*s);
				// Pripocteni pres vstup do pole statistickych dokumentu:
				dokumentystat[i] = new prostorDokument::StatistickyDokument<prostorVstup::Slovo>(*vstupstatdokument);
				// Smazani docasneho vstupu dokumentu:
				delete vstupstatdokument;
					//dokumentystat[i] = new prostorDokument::StatistickyDokument<prostorVstup::Slovo>(prostorVstup::VstupPDT<prostorVstup::Slovo>(*s));

				// Vytvoreni AVL_Vandas vektoru z dokumentu. Typ AVL_Vandas ma dobre definovany aritmeticke operace:
				vektorydokumentu[i] = new prostorAVL::AVL_Vandas<prostorVstup::Slovo>(*dokumentystat[i]);

				// Pripocteni tf z aktualniho dokumentu do celkove sumy tf (potreba pro citatel idf):
				(*tf) += *(vektorydokumentu[i]);

				// Do pomocneho pole si ulozime, jaka vsechna slova se nachazela v aktualnim dokumentu i:
				(*pomocne) = *(vektorydokumentu[i]);

				// V pomocnem poli zmenime cetnost vsech slov na 1 (1 pro jsou v dokumentu, implicitne 0 pro nejsou:
				(*pomocne) = 1;

				// Do pole vndokumentech, ktere bude pozdeji jmenovatelem pro idf, pricteme, jestli slovo v dokumentu bylo:
				(*vndokumentech) += (*pomocne);

				// Vypis Statistickych informaci, at uzivatel vidi, ze se neco deje:
				cout << "Nacten dokument " << *s << " (krok " << (i+1) << ". ze " << pocetvstupu << ")" << endl;
				cout << "Dokument ma " << dokumentyobyc[i]->VratPocetVet() << " vet a " << dokumentyobyc[i]->VratPocetSlov() << " slov (celkem " << dokumentystat[i]->VratPocetOriginalnichSlov() << " originalnich)" << endl << endl;

				// Nacteni dalsiho jmena souboru:
				s = avl_adresar.VratDalsi();
			}


			// Nacteni pole pro idf:
			prostorAVL::AVL_Vandas<prostorVstup::Slovo>* idf = new prostorAVL::AVL_Vandas<prostorVstup::Slovo>();

			// Pripocteni citatele:
			(*idf) = (*tf);

			// Vydeleni jmenovatelem:
			(*idf) /= (*vndokumentech);

			// Zlogaritmovani pole, dle vzorecku:
			idf->AplikujUnarniFunkciNaCetnost(log);

			// -- KONEC NACITACIHO A TRENOVACIHO MODULU.



			// Rozsireni dokumentu o idf
			for(unsigned int i=0; i<pocetvstupu; ++i){
				(*vektorydokumentu[i]) *= (*idf);
				if(!((vektorydokumentu[i])->ZkontrolujRozdil())){
					cerr << "i = " << i << "; vektorydokumentu[i] : Nepodarilo se spravne zkontrolovat kontrolni soucet!" << endl;
				}
			}
			// Nyni jsou v promenne vektorydokumentu[i] hodnoty tf*idf pro kazdy soubor.

			// Hlavni informace o i-tem dokumentu jsou nyni rozlozeny do dvou poli : do dokumentyobyc[i] a do vektorydokumentu[i].
						
			// Zapsani idf na disk + informace o tom, ktere soubory byly zahrnuty, jejich upravena verze...
			// Nacteni idf a informace o tom, ktere soubory jiz byly nacteny (potrebujeme i originaly, takze je nutne pri ukladani
			// ulozit i puvodni soubor, ale proboha ne v PDT formatu!

			// CLUSTEROVACI MODUL:

			prostorCluster::Clustery<prostorVstup::Slovo> clustery(0, 0);
			for(unsigned int i=0; i<pocetvstupu; ++i){
				clustery.PridejDokument(*dokumentystat[i], idf);
			}

			//(*dokumentystat[0],20);
			//cluster.PridejDokument(*dokumentystat[0]);
			//cluster.PridejDokument(*dokumentystat[1]);


			// V clusterovacim modulu musim z kazdeho souboru ziskat jeho centroid. Z prvniho je to vpodstate vektor jeho tf*idf.
			// Kazdy dalsi soubor porovnam s timto(a dalsimi posleze) centroidem a je-li soucin definovany jako (* na tabuli) a vyjde vice nez SIMILARITY
			// TRESHOLD, patri dokument do stejneho clusteru. V tom pripade ho pridame do nejake kolekce a aktualizujeme podle nej
			// centroid. To probehne tak, ze se uvazi vazeny prumer jeho souradnic, s tim, ze puvodni vynasobime *(n/(n+1)) a novy pouze
			// vydelime pomoci vzorecku *(1/(n+1)). Nesmim zapomenout, pokud je omezen pocet slov ve vektoru clusteru, ze je musim orezat.

			// Nakonec pouze vezmu soubor a porovnam jej stejnymi metodami, jako soubory driv s clustery. Ke kteremu clusteru je nejblize,
			// tak z toho vezmu ohodnoceni a podle nej soubor ohodnotim. Asi nejspis toho ohodnoceni zahrnu do stromu AVL_Vandas tak,
			// aby bylo nasledne prohledavani prvku co nejrychlejsi. Nakonec mam soubor, ktery je ohodnoceny. Toto ohodnoceni preklopim
			// zpet do struktury typu ObycejnyDokument, tu budu v poslednim, sumarizacnim kroku, pouzivat nejvice.

			// -- KONEC CLUSTEROVACIHO MODULU.




			// SUMARIZACNI MODUL:

			// Podle zvolene metody

			// -- KONEC SUMARIZACNIHO MODULU.



			/* Jenom testy pro spravnou funkcnost:
			prostorAVL::AVLUzel<prostorVstup::Slovo> * q = idf->Najdi(prostorVstup::Slovo(".","Z"));
			
			if(!(idf->ZkontrolujRozdil())){
				cerr << "idf : Nepodarilo se spravne zkontrolovat kontrolni soucet!" << endl;
			}*/
			
			cout << clustery.VratPocet() << endl;
			cout << "Ahoj" << endl;

		
		}catch(TVyjimka x){
			cout << x << endl;
			getchar();
			return -1;
		};


		try{
			// Odalokace dynamickych promennych:

			for(unsigned int i=0; i < pocetvstupu; ++i){
				//vstupyobyc[i] = new prostorVstup::VstupPDT<prostorVstup::FSlovo>(*s);
				//vstupystat[i] = new prostorVstup::VstupPDT<prostorVstup::Slovo>(*s);

				delete dokumentyobyc[i];
				delete dokumentystat[i];
				//delete vektorydokumentu[i];
			}

			free(dokumentyobyc);
			free(dokumentystat);
			free(vektorydokumentu);


		}catch(TVyjimka x){
			// Pokud se nam nepovedlo mazani a vyskocila nam vyjimka typu TVyjimka, nekde jsme neco nesmazali, koncime s CHYBOU:
			cout << x << endl;
			getchar();
			return -1;
		}

		// Sem se dostane program pouze v pripade, ze dealokace probehla uspesne:
		cout << "Dealocation of memory has been done successfully (no complication detected)!" << endl;
		getchar();
		return 0;
	}catch(...){
		cout << "Program has been terminated by exception coming outside of this program!" << endl;
		return -1;
	}
}
